力扣(LeetCode)84. 柱状图中最大的矩形 (C++)

朴素思想

朴素思想，找左右边界，依次乘以区间内最小上边界，取最大值。这个做法需要遍历左边界，对于每个左边界遍历右边界。因此需要 $O(n^2)$ 的时间复杂度。

转换思路，确定上边界，找左右边界。这个做法可以确定上边界后，往左右扩张边界，时间复杂度也是 $O(n^2)$ 。

顺着确定上边界的思路，可以一次遍历确定所有柱子的左边界。同理确定右边界。(单调栈)

单调栈思路

看看左边界。每遍历一个柱子，在它左侧找矮于当前柱子的第一个柱子，左一矮柱和当前柱子之间都是高柱子，可以围成矩形。然而高柱子，对于右侧柱子就没用了——右侧高于当前柱子的，会卡在当前柱子 ；右侧矮于当前柱子的，不会被高柱子卡。

上述过程抽象成，维护单调栈 $stk$ 将栈顶高于当前柱子的弹栈(高柱子无用论)，将遍历的柱子入栈(用来卡后面的柱子)。维护数组 $left$ 保存所有柱子的左边界，当栈内没有柱子，说明左侧柱子卡不住当前柱子，左边界记为 $-1$ ；当栈顶有柱子，就是这个柱子卡了当前柱子，左边界记为栈顶柱子。

提示 : 栈里存柱子的下标。

同理，维护数组 $right$ 从右到左遍历，确定所有柱子的右边界。
最后，一次遍历所有柱子，维护 $ans$ 保存最大面积，面积 $=$ 高 $\times$ (左边界-右边界) 。恭喜你，解题成功~

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        int n = h.size();
        stack<int> stk;//维护最大最远下标,先左,后右
        vector<int> left(n),right(n);
        for(int i = 0 ;i<n;i++){
            while(stk.size()&&h[stk.top()]>=h[i]) stk.pop();
            if(stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }
        stk = stack<int>();
        for(int i = n-1 ; i>=0;i--){
            while(stk.size()&&h[stk.top()]>=h[i]) stk.pop();
            if(stk.empty()) right[i] = n;
            else right [i ] = stk.top();
            stk.push(i);
        }
        int ans = 0 ;
        for(int i = 0 ;i<n;i++)
            ans = max(ans,(right[i]-left[i]-1)*h[i]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度: $O(n)$ ， $n$ 是柱子的数量，每个柱子的下标最多入栈和出栈一次，时间复杂度是 $O(n)$ 。

空间复杂度: $O(n)$ ，栈和左右边界数组的空间复杂度 $O(n)$ 。

致语

• 理解思路很重要！
• 欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC