LC

题目

思路

单调栈的一个经典应用。

单调栈用来解决类似求某个位置离它最近的比它大/小的元素的位置，并且时间复杂度是O(1)的。

和前缀和类似，利用单调栈先预处理出来一个记录每个元素离它最近的比它大/小的元素的位置，然后求解过程中只需要查表即可。

代码

时间复杂度： 预处理$O(n)$， 遍历每个柱子$O(n)$。总体$O(n)$。

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        stack<int> stk;
        int n = h.size();
        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 res = 0;
        for(int i = 0; i < n; i++) {
            res = max(res, h[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
};