重庆网站建设找重庆最佳科技,建分类网站得花多少钱,wordpress 播放列表,app开发有限公司一、题目描述
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。 示例 1: 输入#xff1a;heights [2,1,5,6,2,3]
输出#xff1a;10
解释#xff1a…一、题目描述
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。 示例 1: 输入heights [2,1,5,6,2,3]
输出10
解释最大的矩形为图中红色区域面积为 10示例 2 输入 heights [2,4]
输出 4提示
1 heights.length 1050 heights[i] 104
二、思路分析
使用栈空间来解决本题通过空间换时间的方式。
三、代码参考
1、Java
class Solution {public int largestRectangleArea(int[] heights) {// 获取数组长度int len heights.length;// 数组长度为 0 或者 1 时直接返回if(len 0){return 0;}if(len 1){return heights[0];}// 用来返回最大面积初始值为 0int area 0;// 创建栈空间做辅助DequeInteger stack new ArrayDeque();// 循环遍历数组for(int i 0; i len; i){// while(!stack.isEmpty() heights[stack.peekLast()] heights[i]){// 获取栈顶高度并移除当前栈顶int height heights[stack.removeLast()];// 做特殊的处理如果当前栈顶的高度和上一个栈顶的高度相同则也需要进行弹栈while(!stack.isEmpty() heights[stack.peekLast()] height){// 移除栈顶元素stack.removeLast();}// 创建宽度变量初始值为 0int width 0;// 如果栈为空说明有效柱体能够从 i 的左边一直延伸到第一个开始if(stack.isEmpty()){// 所以此时的宽度为 iwidth i;}else {width i - stack.peekLast() - 1;}// 计算面积, 长 * 宽并获取最大面积area Math.max(area, height * width);}// 将下标存入栈空间中stack.addLast(i);}// 将当前栈中的所有元素弹出while(!stack.isEmpty()){// 获取栈顶高度并移除当前栈顶int height heights[stack.removeLast()];// 做特殊的处理如果当前栈顶的高度和上一个栈顶的高度相同则也需要进行弹栈while(!stack.isEmpty() heights[stack.peekLast()] height){// 移除栈顶元素stack.removeLast();}// 创建宽度变量初始值为 0int width 0;// 如果栈为空说明有效柱体能够从 i 的左边一直延伸到第一个开始if(stack.isEmpty()){// 所以此时的宽度为 lenwidth len;}else {width len - stack.peekLast() - 1;}// 计算面积, 长 * 宽并获取最大面积area Math.max(area, height * width);}// 返回面积结果return area;}
}
2、Python
class Solution:def largestRectangleArea(self, heights: List[int]) - int:size len(heights)area 0stack []for i in range(size):while len(stack) 0 and heights[i] heights[stack[-1]]:height heights[stack.pop()]while len(stack) 0 and height heights[stack[-1]]:stack.pop()if len(stack) 0:width i - stack[-1] - 1else:width iarea max(area, height * width)stack.append(i)while len(stack) 0 is not None:height heights[stack.pop()]while len(stack) 0 and height heights[stack[-1]]:stack.pop()if len(stack) 0:width size - stack[-1] - 1else:width sizearea max(area, height * width)return area
