题目链接:84. 柱状图中最大的矩形 - 力扣(LeetCode)
要找最大的矩形就是要找以每根柱子为高度往两边延申的边界,要作为柱子的边界就必须高度不能低于该柱子,否则矩形无法同高,也就是需要找出以每根柱子为高、往两边找更低的柱子作为当前矩形的边界(不含)
可以用一个单调递增栈,存储下标,一直记录更高的柱子,一旦碰到低的柱子,此时栈顶可作为矩形的高,当前柱子作为右边界(不含),栈顶往下一个元素可作为左边界(不含),计算完成后弹出栈顶,这样可以以每个柱子的高度为矩形的高计算一次面积,且边界都是尽可能延申的
class Solution {
public:
int largestRectangleArea(vector<int> &heights) {
int ans = 0;
heights.insert(heights.begin(), 0); // 尾哨兵
heights.push_back(0); // 头哨兵
stack<int> plus; // 单调递增栈
for (int i = 0; i < heights.size(); i++) {
while (!plus.empty() && heights[i] < heights[plus.top()]) { // 找到更低的了,说明找到边界
int height = heights[plus.top()];
plus.pop();
ans = max(ans, height * (i - plus.top() - 1));
}
plus.push(i);
}
return ans;
}
};