How does the dynamic programming pattern apply to Trapping Rain Water?

Dynamic programming stores maximum heights to the left and right of each bar to calculate trapped water efficiently, avoiding repeated scans for each index.

Can I solve this problem with constant space?

Yes, the two-pointer approach maintains left_max and right_max variables only, achieving O(1) space while still computing trapped water correctly.

Why does the monotonic stack method work for this problem?

The stack identifies previous peaks and local valleys, modeling state transitions between bars and ensuring each trapped unit is counted precisely once.

What edge cases should I watch for in Trapping Rain Water?

Watch arrays with all equal heights, strictly increasing or decreasing heights, and single or multiple peaks that can cause zero or partial water trapping.

How do I calculate trapped water for irregular valleys?

Use precomputed left and right max or a stack to dynamically assess the bounding heights, ensuring even uneven dips are measured correctly for trapped water.

#42

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：输入： height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出： 6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况…

数组双指针动态规划栈单调栈

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

lightbulb

解题思路

方法一：动态规划

我们定义 $left[i]$ 表示下标 $i$ 位置及其左边的最高柱子的高度，定义 $right[i]$ 表示下标 $i$ 位置及其右边的最高柱子的高度。那么下标 $i$ 位置能接的雨水量为 $\min(left[i], right[i]) - height[i]$ 。我们遍历数组，计算出 $left[i]$ 和 $right[i]$ ，最后答案为 $\sum_{i=0}^{n-1} \min(left[i], right[i]) - height[i]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left = [height[0]] * n
        right = [height[-1]] * n
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
            right[n - i - 1] = max(right[n - i], height[n - i - 1])
        return sum(min(l, r) - h for l, r, h in zip(left, right, height))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand why precomputing left and right max heights ensures correct trapped water calculation?
question_mark
Can you explain how two-pointer traversal reduces space usage while maintaining accurate state transitions?
question_mark
Will you handle edge cases where consecutive bars are equal or the array has a single peak?

warning

常见陷阱

外企场景

error
Failing to update left_max or right_max properly, causing underestimation of trapped water in valleys.
error
Confusing index distances when using the stack approach, leading to overcounting trapped units.
error
Assuming all dips trap water without considering the bounding higher bars, which results in incorrect totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute trapped water when elevation map elements are floating-point heights instead of integers.
arrow_right_alt
Calculate trapped water using only constant extra space without modifying the original array.
arrow_right_alt
Determine the maximum single valley water accumulation instead of total trapped water.

help

常见问题

外企场景

继续练习

#85 最大矩形 #321 拼接最大数 #581 最短无序连续子数组