LeetCode Trapping Rain Water：雙指針與前後綴最大值法

方法二：雙指針 O(1) 空間（最優）

維護 `left, right` 指針及 `lmax, rmax`：

int trap(vector& h) {
    int l=0, r=h.size()-1, lmax=0, rmax=0, ans=0;
    while (l <= r) {
        if (h[l] <= h[r]) {
            if (h[l] >= lmax) lmax = h[l];
            else ans += lmax - h[l];
            l++;
        } else {
            if (h[r] >= rmax) rmax = h[r];
            else ans += rmax - h[r];
            r--;
        }
    }
    return ans;
}

原理分析

• 雙指針法利用「較矮側的最高牆決定該側積水」
• 當 `h[l] <= h[r]` 時，`lmax` 必定 ≤ 真實右側最高，故 `lmax - h[l]` 是準確積水
• 反之同理，逐步收縮區間，單次遍歷完成

關鍵點總結

1. 短板效應：積水高度由雙側最高牆較矮者決定
2. 前後綴分解：將全局依賴拆解為左/右獨立預計算
3. 雙指針優化：利用單調性消除額外空間，單遍歷完成
4. 邊界處理：空數組、單元素直接返回 0

此題是「前後綴分解」與「雙指針優化」的教科書級案例，掌握其從 O(N) 空間到 O(1) 空間的推導過程，可觸類旁通解決眾多區間極值問題。