84.柱状图中最大的矩形
有了之前单调栈的铺垫,这道题目就不难了。
今天是训练营最后一天,恭喜坚持两个月的录友们,接下来可以写一篇自己 代码随想录一刷的总结。好好回顾一下,这两个月自己的博客内容,以及自己的收获。
Python:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.insert(0, 0)
heights.append(0)
n = len(heights)
stk = [0]
result = 0
for i in range(1, n):
while stk and heights[i] < heights[stk[-1]]:
mid_height = heights[stk[-1]]
stk.pop()
if stk:
area = (i - stk[-1] - 1) * mid_height
result = max(result, area)
stk.append(i)
return result
C++:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0);
heights.push_back(0);
stack<int> stk;
stk.push(0);
int result = 0;
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[stk.top()]) {
int h = heights[stk.top()];
stk.pop();
int w = i - stk.top() - 1;
result = max(result, w*h);
}
stk.push(i);
}
return result;
}
};