LeetCode 解題：Trapping Rain Water（接雨水）

這道題最直觀的做法類似 Longest Palindromic Substring 的中心擴展法：對每根柱子向左右掃描，找到其能承接的最大水位，累加得總水量。單次掃描 O(n)，共 n 根柱子，總複雜度 O(n²)，空間 O(1)。

動態規劃優化（雙向掃描）

優化思路：維護一個長度 n 的陣列，進行兩次掃描。第一次從左向右，記錄每根柱子左側的最高高度；第二次從右向左，記錄右側最高高度，並取左右較小者作為該柱子的「瓶頸」高度。兩遍掃描後即可得每根柱子的最大接水量，時間複雜度 O(n)，空間複雜度 O(n)。

代碼實現

public int trap(int[] A) {
    if (A == null || A.length == 0) return 0;
    int max = 0;
    int res = 0;
    int[] container = new int[A.length];
    // 左向右掃描：記錄左側最大高度
    for (int i = 0; i < A.length; i++) {
        container[i] = max;
        max = Math.max(max, A[i]);
    }
    max = 0;
    // 右向左掃描：取左右較小者，累加水量
    for (int i = A.length - 1; i >= 0; i--) {
        container[i] = Math.min(max, container[i]);
        max = Math.max(max, A[i]);
        res += container[i] - A[i] > 0 ? container[i] - A[i] : 0;
    }
    return res;
}

這是一種常見技巧：從兩端各掃描一次獲取決策所需的邊界資訊，適用於當前元素需依賴兩側資訊的問題。類似題目有 Candy（分糖果）。