42. Trapping Rain Water

Hard
Description

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

Example:

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

Intuition#

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

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

Approaches#

1: Dynamic Programming（前後綴最大值）#

  • 概念: 預先計算每個位置的左側最大值和右側最大值陣列，再逐位計算可接水量
  • 時間複雜度: O(n) - 三次線性掃描
  • 空間複雜度: 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#

  • 概念: 左右指針從兩端開始，維護 leftMax 和 rightMax。若 leftMax <= rightMax，左側是瓶頸，處理左指針位置；反之處理右指針位置
  • 時間複雜度: O(n) - 每個位置處理一次
  • 空間複雜度: 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
    }
}
補充：Monotonic Stack 解法

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

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
    }
}
  • 時間複雜度: O(n) - 每個元素最多入棧出棧各一次
  • 空間複雜度: O(n) - 堆疊空間

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

🔑 Takeaways#

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