84. 柱状图中最大的矩形

84. 柱状图中最大的矩形:

题目链接 :84. 柱状图中最大的矩形

题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。


思路:

1、单调栈+哨兵:

(1)矩形面积的计算=底*高,这是毋庸置疑的,那么需要的到三个参数:左边界、右边界、高、
84. 柱状图中最大的矩形

(2)我们的策略是将所以单位宽度为1的矩形的高都压入一个单调栈,即每个高只进入栈中一次。

(3)将入栈元素与当前遍历得到元素进行比较:

(4)当前元素<栈顶元素:栈顶元素出栈作为目标矩形的高参与运算,因为此时当前元素的下标为目标矩形的右边界

(5)当前元素>=栈顶元素,说明以栈顶元素为高的矩形的右侧边界还没找到,当前元素压栈,继续判断。(这里大小的判断条件里包含了两元素相等的可能,是因为边界的确定条件必须是严格小于当前元素,我们才能最终确定矩形的宽。)

2、哨兵优化

(1)因为这种策略我们维护的是一个值递增的栈,一次遍历之后,可能遇到始终无法计算宽度的栈中元素,因为他们找不到自己的右边界(小于它高的元素),为了达到清空栈的目的,需要找到比它值更小的元素

(2)于是我们利用两个0哨兵,分别位于数组最左侧和最右侧,用来凑齐栈内元素的左右边界。

84. 柱状图中最大的矩形


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;
    }
}
上一篇:2021-10-20


下一篇:c和指针第六章第一题