给定非负整数数组 heights
,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1
。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4] 输出: 4
提示:
1 <= heights.length <=105
0 <= heights[i] <= 104
注意:本题与主站 84 题相同: https://leetcode.cn/problems/largest-rectangle-in-histogram/
## 解法 ### **Python3** ```python### **Java**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```java
我们遍历每个柱体,若当前的柱体高度大于等于栈顶柱体的高度,就直接将当前柱体入栈,否则若当前的柱体高度小于栈顶柱体的高度,说明当前栈顶柱体找到了右边的第一个小于自身的柱体,那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxarea = 0;
stack<int> s;
heights.insert(heights.begin(), 0);
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
while (!s.empty() && heights[i] < heights[s.top()]) {
int h = heights[s.top()];
s.pop();
maxarea = max(maxarea, h * (i - s.top() - 1));
}
s.push(i);
}
return maxarea;
}
};