LeetCode Trapping Rain Water：雙指針/動態規劃/單調棧三種解法全解析

題目回顧

給定非負整數數組 height 代表柱狀圖高度，計算下雨後能接住多少雨水。

核心原理：木桶效應

位置 i 能接的水量 = min(左側最高, 右側最高) - height[i]（若為負則為 0）。

解法一：動態規劃預計算左右最高（O(n) 時間 O(n) 空間）

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        if (n == 0) return 0;
        vector left_max(n), right_max(n);
        left_max[0] = height[0];
        for (int i = 1; i < n; ++i)
            left_max[i] = max(left_max[i-1], height[i]);
        right_max[n-1] = height[n-1];
        for (int i = n-2; i >= 0; --i)
            right_max[i] = max(right_max[i+1], height[i]);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += max(0, min(left_max[i], right_max[i]) - height[i]);
        return ans;
    }
};

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

維護 left, right 指針及 left_max, right_max。
關鍵觀察：若 height[left] < height[right]，則 left_max 決定 left 處水量（因右側有更高牆保證），可直接結算 left 並 left++；反之同理。

class Solution {
public:
    int trap(vector& height) {
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0, ans = 0;
        while (left <= right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) left_max = height[left];
                else ans += left_max - height[left];
                ++left;
            } else {
                if (height[right] >= right_max) right_max = height[right];
                else ans += right_max - height[right];
                --right;
            }
        }
        return ans;
    }
};

解法三：單調遞減棧（橫向切分視角）

維護索引單調遞減棧。遍歷時，若當前高度 > 棧頂高度，彈出棧頂 bottom，新棧頂 left 為左邊界，當前 right 為右邊界，可計算 bottom 上方的水槽：
寬 = right - left - 1，高 = min(height[left], height[right]) - height[bottom]。

class Solution {
public:
    int trap(vector& height) {
        stack st;
        int ans = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int bottom = st.top(); st.pop();
                if (st.empty()) break;
                int left = st.top();
                int h = min(height[left], height[i]) - height[bottom];
                int w = i - left - 1;
                ans += h * w;
            }
            st.push(i);
        }
        return ans;
    }
};

三種解法對比

Python 雙指針版（推薦）

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = ans = 0
        while left <= right:
            if height[left] < height[right]:
                if height[left] >= left_max: left_max = height[left]
                else: ans += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max: right_max = height[right]
                else: ans += right_max - height[right]
                right -= 1
        return ans

測試用例

assert Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
assert Solution().trap([4,2,0,3,2,5]) == 9
assert Solution().trap([]) == 0
assert Solution().trap([5,4,3,2,1]) == 0