84. 柱状图中最大的矩形:
题目链接 :84. 柱状图中最大的矩形
题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
思路:
1、单调栈+哨兵:
(1)矩形面积的计算=底*高,这是毋庸置疑的,那么需要的到三个参数:左边界、右边界、高、
(2)我们的策略是将所以单位宽度为1的矩形的高都压入一个单调栈,即每个高只进入栈中一次。
(3)将入栈元素与当前遍历得到元素进行比较:
(4)当前元素<栈顶元素:栈顶元素出栈作为目标矩形的高参与运算,因为此时当前元素的下标为目标矩形的右边界
(5)当前元素>=栈顶元素,说明以栈顶元素为高的矩形的右侧边界还没找到,当前元素压栈,继续判断。(这里大小的判断条件里包含了两元素相等的可能,是因为边界的确定条件必须是严格小于当前元素,我们才能最终确定矩形的宽。)
2、哨兵优化
(1)因为这种策略我们维护的是一个值递增的栈,一次遍历之后,可能遇到始终无法计算宽度的栈中元素,因为他们找不到自己的右边界(小于它高的元素),为了达到清空栈的目的,需要找到比它值更小的元素
(2)于是我们利用两个0哨兵,分别位于数组最左侧和最右侧,用来凑齐栈内元素的左右边界。
AC代码:
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> dq=new Stack<>();
int[] ans =new int[heights.length+2];
for(int i=0;i<heights.length;i++)
{
ans[i+1]=heights[i];
}
heights=ans;
dq.add(0);
int maxArea=0;
for(int i=1;i<heights.length;i++)
{
while(heights[dq.peek()]>heights[i])
{
int height=heights[dq.pop()];
int width=i-dq.peek()-1;
maxArea=Math.max(maxArea,height*width);
}
dq.push(i);
}
return maxArea;
}
}