42. [H] Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

扫描法

从左往右扫描，记录最近一次的最高点。累积水量是根据当前点和最近一次记录到的最高点的差额来计算，如果当前点较低则累计水量，否则则更新最高点的记录。

从左往右扫描，然后反方向从右往左再扫一次。注意，一次是遇到“更高点”的时候计算，一次是遇到“相等高度或更高点”的时候计算，这样避免等高点重复计算。

时间复杂度 O(n)，空间复杂度 O(1)

// 1ms
class Solution {
    public int trap(int[] height) {
        int capacity = 0;
        for (int i = 0, j = 0; i < height.length; i++) {
            if (height[i] >= height[j]) {
                for (int k = j; k < i; k++) {
                    capacity += height[j] - height[k];
                }
                j = i;
            }
        }
        for (int i = height.length-1, j = height.length-1; i >= 0; i--) {
            if (height[i] > height[j]) {
                for (int k = j; k > i; k--) {
                    capacity += height[j] - height[k];
                }
                j = i;
            }
        }
        return capacity;
    }
}

两侧夹逼法

与前述思路类似，根据最近一次记录到的最高点计算累积水量。只是同时从两侧往中心夹逼计算。夹逼的最高点三种情况：

• 最高点在最右侧

• 最高点在最左侧

• 最高点在中部

左右两侧必有一侧较低（或等高），始终移动较低的一侧，同时根据记录的左右最高点计算累计水量。

时间复杂度 O(n)，空间复杂度 O(1)

// 0ms
class Solution {
    public int trap(int[] height) {
        if (height.length < 2) {
            return 0;
        }
        
        int capacity = 0;
        int l = 0, r = height.length-1;
        int lx = height[l], rx=height[r];
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] > lx) {
                    lx = height[l];
                } else {
                    capacity += lx - height[l];
                }
                l++;
            } else {
                if (height[r] > rx) {
                    rx = height[r];
                } else {
                    capacity += rx - height[r];
                }
                r--;
            }
        }
        return capacity;
    }
}