84. 柱状图中最大的矩形
3 min
题目
解法：单调栈
思路
核心思想是维护一个单调递增的栈，通过哨兵触发计算。当遇到更矮柱子时，弹出栈顶并计算以该柱子为高的最大矩形面积。
正确性基于：弹出时，当前索引是右边界，新栈顶是左边界，两者之间的高度由被弹出的柱子决定，这保证了计算的是该高度下的最大宽度。每个柱子仅处理一次，不会遗漏最优解。
- Step 1: 在数组末尾添加高度为0的哨兵，确保所有元素最终会被弹出
- Step 2: 遍历每个柱子索引i
- Step 3: 当栈非空且当前柱子高度小于栈顶柱子高度时，循环弹出栈顶
- Step 4: 对每个弹出的柱子，计算其高度h和宽度（i - left - 1），更新最大面积
- Step 5: 将当前索引i压入栈中
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.push_back(0); // 哨兵，强制把栈里剩余元素处理掉
int ans = 0;
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int h = heights[st.top()];
st.pop();
int left = st.empty() ? -1 : st.top();
int width = i - left - 1;
ans = max(ans, h * width);
}
st.push(i);
}
return ans;
}
};