84.柱状图中最大的矩形
力扣题目链接(opens new window)
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
- 1 <= heights.length <=10^5
- 0 <= heights[i] <= 10^4
-
初始化栈和最大面积变量:
- 创建一个空栈
stack
来存储柱子的索引。 - 初始化一个变量
max_area
用于存储遍历过程中计算出的最大面积。
- 创建一个空栈
-
处理每个柱子:
- 遍历每个柱子的高度
heights
,同时在heights
的末尾添加一个高度为 0 的柱子,以确保栈中的所有柱子都能被处理。 - 对于每个柱子
i
:- 当栈不为空且当前柱子的高度
heights[i]
小于栈顶柱子的高度时,执行以下操作:- 弹出栈顶元素,该元素索引记为
top
。这意味着以heights[top]
为高的矩形的右边界已经确定。 - 计算矩形的宽度:
- 如果栈为空,宽度即为当前柱子的索引
i
(因为左边界是起始位置)。 - 如果栈不为空,宽度为
i - stack[-1] - 1
(当前索引减去新的栈顶元素索引,减去1表示两个柱子间的距离)。
- 如果栈为空,宽度即为当前柱子的索引
- 计算矩形面积:
heights[top] * 宽度
,并更新max_area
。
- 弹出栈顶元素,该元素索引记为
- 将当前柱子索引
i
压入栈中。
- 当栈不为空且当前柱子的高度
- 遍历每个柱子的高度
-
返回最大面积:
- 经过上述遍历,我们已经计算出了每个可能的矩形的面积,并记录了其中的最大值。
- 返回
max_area
作为结果。
class Solution:
def largestRectangleArea(self, heights):
stack = []
max_area = 0
heights.append(0) # 添加一个高度为0的柱子,确保所有柱子都被弹出
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# solution = Solution()
# example_heights = [2, 1, 5, 6, 2, 3]
# result = solution.largestRectangleArea(example_heights)
# print(result)