单调栈中保存每个柱子在 heights 中的下标，从栈底到栈顶的元素对应的柱子的高度是单调递增的。
顺序遍历 heights，如果 heights[i] 比栈顶对应柱子高度更小（heights[i] < heights[st.top()]），那么说明 heights[st.top()] 这个高度在当前柱子加入后已经没有了作用（现在最小的高度是当前柱子，那么要算矩形面积的时候也只会用 heights[i] 来作为矩形的高）。
我们每次计算的矩形为 [栈顶元素代表的矩形, i对应的矩形)：
在弹出栈顶元素==后==，矩形的宽（weight）应该为 i - st.top() - 1，如果栈为空了就为 i - (-1) - 1 -> i。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int res = 0;
heights.push_back(-1);
for (int i = 0; i < heights.size(); ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int h = heights[st.top()];
st.pop();
int w = i; // 即 w = i - (-1) - 1
if (!st.empty()) {
w = i - st.top() - 1;
}
res = max(res, h * w);
}
st.push(i);
}
return res;
}
};
|