42.接雨水

双指针法：动态维护左侧最高点（前缀最大值）和右侧最高点（后缀最大值）。 某个位置能接的雨水量，由其左右两端最高柱子中的较矮者决定， 即能接的雨水量 = min(最大前缀, 最大后缀) - 当前的高度。

class Solution {
    /**
     * 双指针法：动态维护左侧最高点（前缀最大值）和右侧最高点（后缀最大值）。
     * 某个位置能接的雨水量，由其左右两端最高柱子中的较矮者决定，
     * 即能接的雨水量 = min(最大前缀, 最大后缀) - 当前的高度。
     */
    public int trap(int[] height) {
        int len = height.length;
        int left = 0, right = len - 1;
        int ans = 0;
        int pre = 0, suf = 0;
        while (left <= right) {
            int i = left >= 0 ? height[left] : -1;
            int j = right < len ? height[right] : -1;
            if (i < j) {
                // 这个位置能接的水的多少由left决定
                if (pre > i) {
                    ans += pre - i;
                }
                pre = Math.max(pre, i);
                left++;
            } else {
                // 这个位置能接多少水由right决定
                if (suf > j) {
                    ans += suf - j;
                }
                suf = Math.max(suf, j);
                right--;
            }
        }
        return ans;
    }
}