接雨水-困难

难度：困难

题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路：
暴力法：循环遍历元素，每个元素的接水量相当于两边最大高度的较小值减去当前元素高度

var trap = function(height) {
    let total = 0;
    height.forEach((item, index) => {
        let leftMax = 0, rightMax = 0;
        for (var i = 0; i <= index; i++) {
            leftMax = Math.max(height[i], leftMax);
        }
        for (var i = index; i < height.length; i++) {
            rightMax = Math.max(height[i], rightMax);
        }
        total += Math.min(leftMax, rightMax) - item
    })
    return total;
};

动态编程：用数组记录从左向右和从右向左的最大可能储水量。

var trap = function(height) {
    const size = height.length;
    let total = 0;
    let leftArr = [height[0]];
    let rightArr = [height[size - 1]];
    for (var i = 1; i < size; i++) {
        leftArr.push(Math.max(height[i], leftArr[i-1]));
        rightArr.push(Math.max(height[size-1-i], rightArr[i-1]));
    }
    for (var i = 0; i < size; i++) {
        total += Math.min(leftArr[i], rightArr[size-1-i]) - height[i];
    }
    return total;
};

如果一侧高度高，则遍历则相对相反的反向比较。比如左侧最大高度小于右侧最大高度，若当前左指针高度小于左侧最大高度，则total加上左侧最大高度-当前左指针高度，否则将最大高度更新为当前左指针高度。

var trap = function(height) {
    let left = 0, right = height.length - 1, left_max = 0, right_max = 0, total = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] < left_max ? total += left_max - height[left] : left_max = height[left];
            left++;
        } else {
            height[right] < right_max ? total += right_max - height[right] : right_max = height[right];
            right--;
        }
    }
    return total;
};