42. Trapping Rain Water

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

42Trapping Rain WaterTwo PointersHardTwo Pointers

給定 n 個非負整數代表寬度為 1 的柱子高度圖，計算下雨後最多能接住多少水。

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

Intuition

TIP

核心思路：每個位置能接的水量 = min(左側最高, 右側最高) - 自身高度，問題在於如何高效求出左右最高值。

對每個位置 i，水位由左右兩側最高柱子中較矮的那個決定
暴力法對每個位置都掃描左右找最大值，O(n^2)
DP 法用兩個陣列預計算 leftMax[] 和 rightMax[]，O(n) 但需 O(n) 空間
雙指針法只維護 leftMax 和 rightMax 兩個變數，依據較小的一側計算水量，O(1) 空間

Approaches

1. Dynamic Programming (prefix/suffix max) — O(n) / O(n)

Idea: 預先計算每個位置的左側最大值和右側最大值陣列，再逐位計算可接水量
Time: O(n) - 三次線性掃描
Space: O(n) - 兩個輔助陣列

class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        if (n == 0) return 0

        val leftMax = IntArray(n)
        val rightMax = IntArray(n)

        leftMax[0] = height[0]
        for (i in 1 until n) {
            leftMax[i] = maxOf(leftMax[i - 1], height[i])
        }

        rightMax[n - 1] = height[n - 1]
        for (i in n - 2 downTo 0) {
            rightMax[i] = maxOf(rightMax[i + 1], height[i])
        }

        var water = 0
        for (i in 0 until n) {
            water += minOf(leftMax[i], rightMax[i]) - height[i]
        }

        return water
    }
}

⭐ 2. Two Pointers — O(n) / O(1)

Idea: 左右指針從兩端開始，維護 leftMax 和 rightMax。若 leftMax <= rightMax，左側是瓶頸，處理左指針位置；反之處理右指針位置
Time: O(n) - 每個位置處理一次
Space: O(1) - 只用常數個變數

class Solution {
    fun trap(height: IntArray): Int {
        var left = 0
        var right = height.size - 1
        var leftMax = 0
        var rightMax = 0
        var water = 0

        while (left < right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left]
                } else {
                    water += leftMax - height[left]
                }
                left++
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right]
                } else {
                    water += rightMax - height[right]
                }
                right--
            }
        }

        return water
    }
}

Note: Monotonic Stack Approach

用遞減單調堆疊，遇到比棧頂高的柱子時，表示形成凹槽可以接水。逐層計算水量（橫向計算）。

class Solution {
    fun trap(height: IntArray): Int {
        val stack = ArrayDeque<Int>() // 存索引
        var water = 0

        for (i in height.indices) {
            while (stack.isNotEmpty() && height[i] > height[stack.last()]) {
                val bottom = stack.removeLast()
                if (stack.isEmpty()) break
                val width = i - stack.last() - 1
                val h = minOf(height[i], height[stack.last()]) - height[bottom]
                water += width * h
            }
            stack.addLast(i)
        }

        return water
    }
}

Time: O(n) - 每個元素最多入棧出棧各一次
Space: O(n) - 堆疊空間

WARNING

雙指針法的關鍵洞察：當 height[left] <= height[right] 時，不管右邊實際最大值是多少，leftMax 就是瓶頸（因為右邊至少有 height[right] >= height[left] >= leftMax 的可能）。所以用 leftMax 計算水量是正確的。

🔑 Takeaways

Pattern: 前後綴最值問題可以用雙指針壓縮到 O(1) 空間——哪邊的最值較小就處理哪邊
Key trick: 理解「瓶頸在較矮一側」的原理是此題核心；此題同時是 DP、Stack、Two Pointers 三種解法的經典練習題

Intuition

Approaches

🔑 Takeaways

相關題目