来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/trapping-rain-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

解答

解题思路：

1. 把问题拆分为每个柱子的该接多少雨水来思考

解法一：

1. 每个柱子能接多少雨水，取决于它左边的最高柱和右边的最高柱
2. 作为性能优化，可以先找出每个条目的左边最高柱和右边最高柱，并缓存起来
3. 然后走一遍所有柱子，通过每根柱子找到其左右两边的最高柱，然后求出差值，差值求和

解法二：

1. 使用双指针解法
2. 左指针和右指针，谁可以走，取决于谁比较低。谁低谁先走
3. 如果走到柱子，小于等于当前最大值，则求差值并求和
4. 如果走到柱子，大于最大值，则更新最大值为当前柱值
5. 当左右指针遇到时结束

解法二为最优解

/**
 * @param {number[]} height
 * @return {number}
*/
var trap = function(height) {
    let returnHeight = 0;
    let start = 0,
        end = height.length - 1,
        lMax = height[start],
        rMax = height[end];
    while (start <= end) {
        if (lMax < rMax) {
            if (height[start] <= lMax) {
                returnHeight += lMax - height[start];
            } else {
                lMax = Math.max(lMax, height[start]);
            }
            start++;
        } else {
            if (height[end] <= rMax) {
                returnHeight += rMax - height[end];
            } else {
                rMax = Math.max(rMax, height[end]);
            }
            end--;
        }
    }
    return returnHeight;
};