42. Trapping Rain Water

This is a problem I've memorized inside out — totally muscle memory. But I revisited it yesterday and tried to actually understand it. I even made a GIF to help myself visualize what's happening. Here's the code:

Let's use the example: [0,1,0,2,1,0,1,3,2,1,2,1]

The core idea of this problem is basically the "bucket theory": We treat the two outermost bars as the "Walls of Maria" — and ignore the inner ones for now. If that's the case, then the max height of water we can hold is min(leftmax, rightmax). In other words, the shorter wall decides the water level.

But height alone isn't enough — we also need width to compute the actual amount of water. So we look at each bar one by one, and calculate how much water we can trap on top of it, then sum it all up.

We use two pointers: left and right, and also keep track of the highest wall on the left (leftmax) and the highest wall on the right (rightmax).

When our pointer reaches the end of the string (or the two walls meet), that means we've gone through all the characters — that's when we know we have a valid answer.

Take this specific frame as an example:

At this point, the max water we can hold is leftmax = 2, but the current column has height 1, so we can trap:

2 - 1 = 1 unit of water.

If we were comparing leftmax and rightmax directly, we wouldn't know why this particular column can hold water. The only reason it can trap water is because its height is less than or equal to leftmax.

Code

class Solution:
    def trap(self, height: list[int]) -> int:
        ans = leftmost = rightmost = 0
        left, right = 0, len(height) - 1
        while left < right:
            leftmost = max(leftmost, height[left])
            rightmost = max(rightmost, height[right])
            if leftmost <= rightmost:
                ans += leftmost - height[left]
                left += 1
            else:
                ans += rightmost - height[right]
                right -= 1
        return ans

import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np

# Given height list for illustration
height = [0,1,0,2,1,0,1,3,2,1,2,1]

# Initialize variables as in the function
left, right = 0, len(height) - 1
leftmax = rightmax = 0
ans = 0

# For animation, store each frame's water level and pointers
frames = []

# Simulate the logic and capture frames
while left < right:
    leftmax = max(leftmax, height[left])
    rightmax = max(rightmax, height[right])
    water = [0] * len(height)
    if leftmax <= rightmax:
        trapped = max(0, leftmax - height[left])
        ans += trapped
        water[left] = trapped
        frames.append((height.copy(), water.copy(), left, right))
        left += 1
    else:
        trapped = max(0, rightmax - height[right])
        ans += trapped
        water[right] = trapped
        frames.append((height.copy(), water.copy(), left, right))
        right -= 1

# Create animation
fig, ax = plt.subplots(figsize=(10, 5))

def update(frame):
    ax.clear()
    heights, water, l_ptr, r_ptr = frame
    indices = np.arange(len(heights))
    ax.bar(indices, heights, color='grey', edgecolor='black')
    ax.bar(indices, water, bottom=heights, color='blue', edgecolor='blue', alpha=0.6)
    ax.axvline(l_ptr, color='green', linestyle='--', label='Left Pointer')
    ax.axvline(r_ptr, color='red', linestyle='--', label='Right Pointer')
    ax.set_ylim(0, max(height) + 3)
    ax.set_title("Trapping Rain Water Animation")
    ax.legend()

ani = animation.FuncAnimation(fig, update, frames=frames, interval=500, repeat=False)

from IPython.display import HTML
ani.save("trapping_rain_water.gif", writer="pillow", fps=2)  # 保存为 GIF

贡献者

longsizhuo贡献 4 次 · 最近 2026/05/06

这篇文章有帮助吗？

42. Trapping Rain Water

QUESTION

My Think

Code

贡献者

最近更新

On this page