代码随想录算法训练营第四十二天 | 单调栈 Part02

380 字

2 分钟

代码随想录算法训练营第四十二天 | 单调栈 Part02

2025-07-29

算法

单调栈、接雨水、柱状图形中最大的矩形

/

LeetCode

/

Python

LeetCode 42. 接雨水#

题目链接

思路总结：

栈中存的是索引，栈顶是当前最低洼的“底”。
若当前高度高于栈顶，说明可以计算雨水面积。
一次计算一个低洼区域，直到无法再接水。
栈中存的是索引，栈顶是当前最低洼的“底”。
若当前高度高于栈顶，说明可以计算雨水面积。
一次计算一个低洼区域，直到无法再接水。

1
class Solution:
2
    def trap(self, height: List[int]) -> int:
3
        stack = []
4
        res = 0
5
        for i in range(len(height)):
6
            # 当前柱子比栈顶高，说明可以接水
7
            while stack and height[stack[-1]] < height[i]:
8
                bottom = stack.pop()  # 取出低洼处
9
                if not stack:
10
                    break  # 左边界不存在，无法接水
11
                left = stack[-1]  # 左边界
12
                width = i - left - 1
13
                bounded_height = min(height[left], height[i]) - height[bottom]
14
                res += width * bounded_height
15
            stack.append(i)
16
        return res

LeetCode 84. 柱状图中最大的矩形#

题目链接

思路总结：

维护一个递增栈，当当前柱子高度变矮时，就结算面积。
每次出栈表示：当前高度无法继续向右延伸了。
高度乘以宽度，更新最大面积。
哨兵元素 0 保证最后栈中元素全部出栈。

1
class Solution:
2
    def largestRectangleArea(self, heights: List[int]) -> int:
3
        stack = []
4
        res = 0
5
        heights.append(0)  # 哨兵，确保栈清空
6
        for i in range(len(heights)):
7
            while stack and heights[stack[-1]] > heights[i]:
8
                h = heights[stack.pop()]
9
                # 计算宽度：如果栈为空，说明左边界为 -1，否则是 stack[-1]
10
                w = i if not stack else i - stack[-1] - 1
11
                res = max(res, h * w)
12
            stack.append(i)
13
        return res