42. Trapping Rain Water

題目 / Problem

中文： 給定 n 個非負整數，代表一張高度圖，每根柱子寬度為 1。請計算下雨後總共能困住多少單位的雨水。

English: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Constraints / 限制： - n == height.length - 1 <= n <= 2 * 10^4 - 0 <= height[i] <= 10^5

Example / 範例：

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

中文說明：把陣列想成柱狀圖，黑色是柱子，下雨後在凹陷處能存下 6 單位的水。 English: Picture the array as bars; rain pools in the dips and 6 units of water are trapped.

名詞解釋 / Glossary

• Elevation map / 高度圖：用陣列表示一排寬度為 1 的柱子，height[i] 是第 i 根柱子的高度。An array where height[i] is the height of the i-th bar of width 1.
• Trapped water at index i / 第 i 格能存的水：等於 min(左邊最高柱, 右邊最高柱) - height[i]（若為負則為 0）。Equals min(maxLeft, maxRight) - height[i], clamped to 0.
• Two pointers / 雙指針：用兩個索引（通常一個從左、一個從右）同時掃描陣列，每步根據條件移動其中一個。Two indices scanning from both ends, advancing whichever side is currently safe to process.
• Invariant / 不變量：演算法執行過程中始終為真的性質，幫助我們證明正確性。A property that always holds during the loop; used to prove correctness.
• Prefix/suffix max / 前綴最大值、後綴最大值：leftMax[i] 表示 height[0..i] 的最大值；rightMax[i] 表示 height[i..n-1] 的最大值。Running max from the left/right side.
• malloc / free：C 語言用來在堆積（heap）上動態配置與釋放記憶體的函式。Allocate / release memory on the heap in C.
• std::vector：C++ 標準庫中的動態陣列，會自動管理記憶體。A dynamic array container from the C++ STL that manages its own memory.

思路

中文： 最直覺的暴力解法：對每一格 i，往左掃一遍找到 leftMax[i]，往右掃一遍找到 rightMax[i]，這格能存的水量就是 min(leftMax[i], rightMax[i]) - height[i]（若為負則為 0）。總和即為答案。這個做法是 O(n²)，當 n = 2×10⁴ 時約四億次操作，太慢。

改進想法一（DP，O(n) 時間、O(n) 空間）：我們其實不需要每次重算左右最大值，只要先用兩次線性掃描預先算好 leftMax[] 和 rightMax[] 陣列，再用一次掃描累加每格水量即可。

進一步改進（雙指針，O(n) 時間、O(1) 空間）：觀察一個關鍵不變量——若 height[left] < height[right]，則右邊一定有一根至少 height[right] 高的柱子擋住水，所以左邊那格能存的水只由左側已知的最大值 leftMax 決定（與右側遠處到底多高無關，只要它 ≥ 當前右指針即可）。因此我們維護兩個指針 left, right 以及兩個變數 leftMax, rightMax，每次處理較矮的那一側並向中間推進。較矮側那格的水量 = 該側目前的 max 減去自己的高度。為什麼這成立？因為對側存在一根 ≥ 當前這一側 max 的柱子，所以「左右兩側最高的最小值」一定等於當前這一側的 max，公式直接成立。

English: Brute force: for each index i, sweep left to find leftMax[i] and right to find rightMax[i], then add max(0, min(leftMax[i], rightMax[i]) - height[i]). That is O(n²) — about 4×10⁸ ops at n = 2×10⁴, far too slow.

First improvement (DP, O(n) time, O(n) space): precompute leftMax[] and rightMax[] with two linear passes, then sum the per-cell contributions in a third pass.

Optimal (two pointers, O(n) time, O(1) space): the key invariant is that if height[left] < height[right], the right side has at least one bar of height height[right] that will block water on the right, so the water trapped above index left depends only on the left-side running max — the exact height further right doesn't matter as long as it is at least the current right value. Maintain pointers left, right and running maxima leftMax, rightMax. Each step process the shorter side: the trapped water there equals sideMax - height[side], then advance that pointer. This works because the other side guarantees a tall enough wall, so min(leftMax, rightMax) on the shorter side simplifies to that side's own running max.

逐步走查 / Walkthrough

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1], n = 12.

Initial: left=0, right=11, leftMax=0, rightMax=0, water=0.

Final water / 最終答案 = 6. ✅

Solution — C

// Algorithm: two-pointer scan. Maintain leftMax and rightMax while
// 演算法：雙指針掃描。維護 leftMax 與 rightMax，
// shrinking the window from both ends. At each step, process the SHORTER side:
// 每步處理較矮的那側：該側的水量 = 該側 max - 當前高度。
// the trapped water at that cell equals sideMax - height[cell]. O(n) time, O(1) space.

int trap(int* height, int heightSize) {
    // Edge case: fewer than 3 bars cannot trap any water.
    // 邊界情況：少於 3 根柱子無法存水。
    if (heightSize < 3) return 0;

    int left = 0;                      // 左指針從最左邊開始 / left pointer starts at index 0
    int right = heightSize - 1;        // 右指針從最右邊開始 / right pointer starts at last index
    int leftMax = 0;                   // 目前左側看過的最高柱 / running max of bars seen from the left
    int rightMax = 0;                  // 目前右側看過的最高柱 / running max of bars seen from the right
    int water = 0;                     // 累積的水量 / accumulated trapped water

    // 當兩指針還沒相遇時繼續 / loop until the two pointers meet
    while (left < right) {
        // 比較兩端高度，永遠處理較矮的那邊 / always work on the shorter side
        if (height[left] < height[right]) {
            // 左邊較矮：先更新 leftMax，再用 leftMax 算這格水量
            // Left side is shorter: update leftMax first, then trap water there.
            if (height[left] >= leftMax) {
                leftMax = height[left]; // 新的左側最高 / new left-side max — this cell traps 0 water itself
            } else {
                // 左側已有更高的牆，這格能存 leftMax - height[left] 水
                // A taller wall exists on the left, so this cell traps leftMax - height[left] units.
                water += leftMax - height[left];
            }
            left++;                    // 左指針前進 / advance the left pointer
        } else {
            // 右邊較矮（或相等）：對稱地處理右側 / right side is shorter (or equal); symmetric logic
            if (height[right] >= rightMax) {
                rightMax = height[right]; // 新的右側最高 / new right-side max
            } else {
                // 右側已有更高的牆，這格能存 rightMax - height[right] 水
                // Right side already has a taller wall, so trap rightMax - height[right] units.
                water += rightMax - height[right];
            }
            right--;                   // 右指針後退 / advance the right pointer leftward
        }
    }

    return water;                      // 回傳總水量 / return the total trapped water
}

Solution — C++

// Algorithm: same two-pointer scan as the C version, written in idiomatic C++.
// 演算法：與 C 版相同的雙指針掃描，採用慣用的 C++ 寫法。
// O(n) time, O(1) extra space. We use std::vector<int> (the input type LeetCode passes in)
// and the standard std::max from <algorithm>.

#include <vector>      // std::vector 動態陣列 / dynamic array container
#include <algorithm>   // std::max 取最大值的工具函式 / utility function for max

class Solution {
public:
    // 函式簽名：接收一個整數向量的 const 參考（避免複製），回傳 int
    // Signature: take a const reference to a vector<int> (no copy), return int.
    int trap(const std::vector<int>& height) {
        const int n = static_cast<int>(height.size()); // 取得長度，轉成 int 方便比較 / size as int
        if (n < 3) return 0;                            // 少於 3 根柱子無法存水 / not enough bars to trap water

        int left = 0;                  // 左指針 / left pointer
        int right = n - 1;             // 右指針 / right pointer
        int leftMax = 0;               // 左側最高柱 / running max from the left
        int rightMax = 0;              // 右側最高柱 / running max from the right
        int water = 0;                 // 答案累加器 / accumulator for trapped water

        // 雙指針向中間靠攏 / pointers move toward each other until they meet
        while (left < right) {
            if (height[left] < height[right]) {
                // 左側較矮 → 處理左格 / left side is shorter, process the left cell
                // std::max(a, b) 回傳 a 與 b 中較大者 / returns the larger of a and b
                leftMax = std::max(leftMax, height[left]);
                water += leftMax - height[left]; // 若 height[left]==leftMax 則加 0 / adds 0 when this cell IS the wall
                ++left;                          // 前綴遞增運算子，比 left++ 略快一些 / pre-increment, idiomatic in C++
            } else {
                // 右側較矮或相等 → 處理右格 / right side is shorter or equal, process the right cell
                rightMax = std::max(rightMax, height[right]);
                water += rightMax - height[right]; // 對稱地累加水量 / symmetric accumulation
                --right;                            // 右指針往左移 / move right pointer leftward
            }
        }

        return water; // 回傳結果 / return the total trapped water
    }
};

複雜度 / Complexity

• Time: O(n) — 每次迴圈我們把 left 或 right 移動一格，兩指針最多總共走 n 步。Each iteration advances exactly one pointer; together they cover n positions, so the loop runs at most n times.
• Space: O(1) — 只用了固定數量的整數變數（left、right、leftMax、rightMax、water），與輸入大小無關。Only a constant number of integer variables; no auxiliary arrays.

Pitfalls & Edge Cases

• 少於 3 根柱子 / Fewer than 3 bars：不可能存水，提前回傳 0 避免不必要的計算。Cannot trap any water; early return prevents wasted work (and is just clearer).
• 平坦或單調陣列 / Flat or monotonic input（如 [1,2,3,4] 或 [3,3,3]）：演算法仍然回傳 0，因為每一格不是等於就是高於目前的 max，max - height = 0. Algorithm naturally returns 0 because every cell either updates the max or equals it.
• 混淆 < 和 <= / Confusing < vs <= in the comparison：當 height[left] == height[right] 時兩條分支都正確，所以用嚴格 < 即可；如果寫成 > 也行，重點是「相等時不要兩邊都做」。When the two heights are equal, either branch is correct — just don't process both sides for one cell.
• 忘記更新 max 再加水 / Updating max after adding water by mistake：必須先 leftMax = max(leftMax, height[left]) 再 water += leftMax - height[left]，否則可能出現負數。Always refresh the running max before computing the diff, otherwise the subtraction could go negative.
• 整數溢位 / Integer overflow：最壞情況 n = 2×10⁴、每格 height ≤ 10⁵，總水量上界約 2×10⁹，剛好接近 int 上限 2.147×10⁹，C/C++ 的 int（32-bit）仍夠用，但若題目放寬限制就要改成 long long. The worst-case sum fits in a 32-bit int here, but it's tight — be ready to switch to long long if constraints grow.
• C 函式簽名 / C signature confusion：LeetCode 的 C 介面是 int trap(int* height, int heightSize)，heightSize 是陣列長度，因為 C 的指標本身不帶長度資訊。LeetCode passes the array length explicitly because raw C pointers carry no size information.