LeetCode 84. 柱状图中最大的矩形
原题链接
困难
作者:
我是java同学
,
2023-10-10 20:34:59
,
所有人可见
,
阅读 43
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
int n = heights.size();
vector<int> l(n), r(n);
for (int i = 0; i < n; i ++ ) {
while (stk.size() && heights[stk.top()] > heights[i]) stk.pop();
if (stk.empty()) l[i] = -1;
else l[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; i -- ) {
while (stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
if (stk.empty()) r[i] = n;
else r[i] = stk.top();
stk.push(i);
}
int res = 0;
for (int i = 0; i < n; i ++ ) {
res = max(res, (r[i] - l[i] - 1) * heights[i]);
}
return res;
}
};