题目链接:剑指 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)\)。