题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
样例
示例1
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例2
输入: heights = [2,4]
输出: 4
C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int res = 0;
vector<int> left(n), right(n);
stack<int> stk;
for (int i = 0; i < n; i ++)
{
while (stk.size() && heights[i] <= heights[stk.top()]) stk.pop();
if (stk.empty()) left[i] = -1;
else left[i] = stk.top(); // 关键步骤, 别漏掉
stk.push(i);
}
while (stk.size()) stk.pop();
for (int i = n - 1; i >= 0; i --)
{
while (stk.size() && heights[i] <= heights[stk.top()]) stk.pop();
if (stk.empty()) right[i] = n;
else right[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; i ++) res = max(res, heights[i] * (right[i] - left[i] - 1));
return res;
}
};