剑指 Offer II 039. 直方图最大矩形面积

题目链接：剑指 Offer II 039. 直方图最大矩形面积

方法：单调栈

解题思路

• 以直方图中的某一条为高的最大(面积)矩形的宽度为 (r - l + 1)，其中 (r) 表示在其右边第一个小于(或等于)当前高度的下标，(l) 表示在其左边第一个小于当前高度下标。
• (l)，(r) 可以利用单调栈在 (O(1)) 时间获取：
  • 单调栈存储单调递增的下标；
  • 若当前下标对应的高度小于栈顶下标对应的高度，则当前下标就是栈顶下标的 (r)；
  • 次栈顶下标就是栈顶下标的 (l)；
• 计算以每个下标为高的矩形面积最大值，答案取其中的最大值。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);
        int ans = 0, n = heights.size();
        for (int i = 0; i < n; i ++ ) {
            while (stk.top() != -1 && heights[stk.top()] >= heights[i]) {
                int h = heights[stk.top()];
                stk.pop();
                ans = max(ans, h * (i - stk.top() - 1));
            }
            stk.push(i);
        }
        while (stk.top() != -1) {
            int h = heights[stk.top()];
            stk.pop();
            ans = max(ans, h * (n - stk.top() - 1));
        }
        return ans;
    }
};

复杂度分析

时间复杂度：(O(n))；
空间复杂度：(O(n))。