LeetCode 84：直方图中的最大矩形 — 逐步可视化追踪

Source: Dev.to

Problem

找到可以在直方图中形成的最大矩形的面积。直方图由一个数组表示，每根柱子的高度为数组中的值，宽度均为 1，且矩形必须由连续的柱子组成。

Approach

使用单调栈来跟踪柱子索引，保持高度递增的顺序。当遇到较短的柱子时，利用栈中之前存储的较高柱子作为高度计算矩形面积，宽度由当前的位置和栈中的内容决定。

Complexity

• Time: (O(n))
• Space: (O(n))

Code

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0

        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        while stack:
            height = heights[stack.pop()]
            width = len(heights) if not stack else len(heights) - stack[-1] - 1
            max_area = max(max_area, height * width)

        return max_area