接雨水问题

[xszi]

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

leetcode

[xszi]

暴力解法 —— 木桶效应

const trap = function(height) {
    let sum = 0
    for(let index = 1; index < height.length-1; index++){
        let leftMax = 0 //找左边最大高度
        for(let i = index-1; i >= 0; i--){
            leftMax = height[i] >= leftMax ? height[i] : leftMax
        }
        let rightMax = 0 //找右边最大高度
        for(let i = index+1; i < height.length; i++){
            rightMax = height[i] >= rightMax ? height[i] : rightMax
        }
        let min = Math.min(leftMax, rightMax) //得到左右两边最大高度中较矮的那个高度
        if(min > height[index]){
            sum = sum + min - height[index] //接水量 = 左右两边最大高度中较矮的那个高度 - 当前项的高度
        }
        //console.log(leftMax, rightMax, sum)
    }
    return sum
};

虚拟值暂存

const trap = function (height) {

    let temp = 0 //当前最高水柱高度
    let virtual = 0 //虚拟值
    let sum = 0 //总值

    //从左向右计算
    for (let i = 0; i < height.length; i++) {
            //如果水柱低于当前最高水柱
            if(temp > height[i]){
                virtual += (temp - height[i]) //虚拟值累加
                //加虚拟值
            }else{ //如果水柱高于或等于当前最高水柱
                //将之前加的虚拟值一并加入总值 并 更新当前最高水柱高度
                temp = height[i]
                sum = sum + virtual
                virtual = 0 //再重新算下一个虚拟值
            }
    }

    //重新初始化值
    virtual = 0
    temp = 0

    //从右向左计算（同上的方法）
    for (let i = height.length; i>=0; i--) {
            if(temp > height[i]){
                virtual += (temp - height[i])
            }else if(temp < height[i]){ //不过这里没有等于条件，防止与上面的重复
                temp = height[i]
                sum = sum + virtual
                virtual = 0
            }
    }

    return sum
};

双指针法

1. 分别设定左右两个指针，按照一定条件往中间移动
2. 如果左边的指针所在高度小于右边，则左指针向右移动，否则右指针向左移动
3. 当左右两个指针所在的高度不为零，左右指针之间有某个位置的高度小于左右指针所在高度的最小值，那这个位置必然可以储水
4. 计算完当前位置储水后，更新左或右指针的位置，

   const trap = function (height) {
   if (height.length < 3) { return 0; }
   let left = 0, length = height.length,
       right = length - 1, sum = 0, 
       tempLeft, tempRight, add;
   while (left < right) {
       add = 0;
       if (height[left] <= height[right]) {
           if (tempLeft === undefined) {
               tempLeft = height[left];
           }
           tempLeft = tempLeft < height[left] ? height[left] : tempLeft;
           add = tempLeft - height[left];
           left++;
       } else {
           if (tempRight === undefined) {
               tempRight = height[right];
           }
           tempRight = tempRight < height[right] ? height[right] : tempRight;
           add = tempRight - height[right];
           right--;
       }
       if (add > 0) {
           sum += add;
       }
   }
   return sum;
   };

[xszi]

数学方法了解一下 数学解法，我秀我自己

如下图，从左往右遍历，不管是雨水还是柱子，都计算在有效面积内，并且每次累加的值根据遇到的最高的柱子逐步上升。面积记为S1。

从左往右遍历得S1，每步S1+=max1且max1逐步增大

同样地，从右往左遍历可得S2。

从右往左遍历得S2，每步S2+=max2且max2逐步增大

于是我们有如下发现，S1 + S2会覆盖整个矩形，并且：重复面积 = 柱子面积 + 积水面积

最终， 积水面积 = S1 + S2 - 矩形面积 - 柱子面积

var trap = function(height) {
  let heightSum = 0
  let maxLeftArea = 0, maxRightArea = 0,
      maxLeftHeight = 0, maxRightHeight = 0
  const len = height.length

  for (let i = 0; i < len; i++) {
    if (height[i] > maxRightHeight) {
      maxRightHeight = height[i]
    }
    if (height[len - 1 - i] > maxLeftHeight) {
      maxLeftHeight = height[len - 1 - i]
    }
    maxRightArea += maxRightHeight
    maxLeftArea += maxLeftHeight
    heightSum += height[i]
  }
  return maxRightArea + maxLeftArea - (maxLeftHeight * len) - heightSum
};