42. 接雨水

1. 前後綴分解

下雨後，一個位置裝的雨水高度，取決於自己左右兩邊的最小值，以及自己當下位置的高度。
因此我們能建立兩個陣列，left[i]紀錄位置i之前的高度最大值，right[i]紀錄位置i以後的高度最大值。
因此對於height[i]來說，自己能承接的雨水，就是min(left[i], right[i])減去自己的高度。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n), right(n);
        left[0] = height[0], right.back() = height.back();
        for(int i = 1; i < n; i++) {
            left[i] = max(left[i - 1], height[i]);
            right[n - i - 1] = max(right[n - i], height[n - i - 1]);
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            res += max(min(left[i], right[i]) - height[i], 0);
        }
        return res;
    }
};

2. 雙指針

在第一種寫法中，每次需要取min(left[i], right[i])，並且我們能確定，left數組必定單調遞增，也就是left[i] >= left[i - 1]越來越大，而right數組必定單調遞減，反過來看也是單調遞增，利用這個性質，我們能將left, right數組用兩個指針表示。

假設數組現在是 $[100,16,90,20,80,70]$ ，
現在left = 0，對應最大值lmax = 100，right = 5，對應最大值rmax = 70。

接下來要移動指針，因為每次會取左右的最小值，因此要盡量移動小的那一邊，
右邊的 70 比較小，右指針往左移動，來到 80，此時我們能確定，
80 這個位置裝載的水量一定是 $\max(\min(100,70)-80,0)) = 0$，
因為對於 50 來說，左側的最大值只會比 100 更多，右側的最大值已經確定是 70。最後更新rmax = 80。

重複步驟直到指針交會，當left > right，就代表每個位置的雨水數值都計算完畢。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 1, right = n - 2;
        int lmax = height[0], rmax = height.back();
        int res = 0;
        while(left <= right) {
            if(lmax <= rmax) { // 比較左右最大值，移動比較小那一邊的指針
                res += max(0, lmax - height[left]); 
                lmax = max(lmax, height[left++]);
            }
            else {
                res += max(0, rmax - height[right]);
                rmax = max(rmax, height[right--]);
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：方法一 $O(n)$，方法二 $O(1)$