长大后想做什么？做回小孩！

0%

LeetCode——柱状图中的最大矩形

发表于 更新于 分类于 Valine：
本文字数： 735

NO.84 柱状图中的最大矩形 困难

Gmq4ud.png

GmqfjH.png

思路一：暴力 遍历每个元素，求以当前元素为矩形高度所能形成的矩形面积。返回最大的面积。

如何求以当前元素为高度形成矩形的长？

向左，找到最后一个大于等于当前元素的位置left。

向右，找到最后一个大于等于当前元素的位置right。

然后right-left+1就是这个形成的矩形的长，然后当前元素*(right-left+1)得到面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int largestRectangleArea(int[] heights) {
    if (heights==null||heights.length==0)return 0;
    int ans=0;
    //遍历
    for (int i = 0; i < heights.length; i++) {
        //找左边最后一个大于等于当前高度的位置
        int left=i;
        while (left>0&&heights[left-1]>=heights[i]){
            left--;
        }
        //找右边最后一个大于等于当前高度的位置
        int right=i;
        while (right<heights.length-1&&heights[right+1]>=heights[i]){
            right++;
        }
        //计算以当前元素作为高形成的矩形的面积
        ans=Math.max(ans,heights[i]*(right-left+1));
    }
    return ans;
}

时间复杂度：O(n^2)

思路二：单调栈

关于单调栈：

  1. 单调递增栈即栈内元素保持单调递增的栈，同理单调递减栈即栈内元素保持单调递减的栈。
  2. 操作规则(下面都以单调递增栈为例)：如果新的元素比栈顶元素大，就入栈；如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小。

初始化一个单调递增栈，遍历参数数组中的元素将符合单调栈的元素的下标入栈。

如果新的元素大于等于栈顶元素，就下标入栈；否则开始将栈中的下标弹出，直到满足新元素大于等于栈顶元素为止。

每次弹出下标时，就用弹出下标对应的元素作为高，形成的矩形的宽就是当前元素和stack[top-1]之间的那些柱子。

即我们弹出stack[top]时，记当前元素在原数组中的下标为i、刚出栈的元素记为stack[top]，当前弹出元素为高的最大矩形面积为heights[stack[top]]*(i-stack[top-1]-1)。

当参数数组遍历完毕，我们将栈中剩余的元素陆续出栈，每个出栈元素都用下面的公式求面积:

heights[stack[top]]*(heights.length-stack[top-1]-1)

tips:栈底先放入一个-1作为辅助，标记栈底。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack=new Stack<>();
    //辅助,标记栈底
    stack.push(-1);
    int maxArea=0;
    //遍历入栈
    for (int i = 0; i < heights.length; i++) {
        //当栈不空并且当前元素不符合单调递增栈的要求
        //就出栈栈顶元素作为高，求形成的矩形最大面积
        while (stack.peek()!=-1&&heights[stack.peek()]>heights[i]){
            maxArea=Math.max(maxArea,heights[stack.pop()]*(i-stack.peek()-1));
        }
        stack.push(i);
    }
    //遍历入栈完毕之后，将栈里的元素陆续出栈并作为高，求形成的矩形最大面积
    while (stack.peek() != -1) {
        maxArea=Math.max(maxArea,heights[stack.pop()]*(heights.length-stack.peek()-1));
    }
    return maxArea;
}

时间复杂度：O(n) 所有元素入队一次，出队一次。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github