双指针经典问题

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

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

双指针

1. 
   

   /**
   * @param {number[]} height
   * @return {number}
   */
   const trap = function(height) {
   let len = height.length;
   if(len < 3) {
    return 0;
   }
   let res = 0;
   let leftMax = height[0];
   let rightMax = height[len - 1];
   // 注意初值的选取，前面做了特判，因此这里不会越界
   // 头和尾都不存雨水
   let left = 1;
   let right = len - 2;
   // 强调：这里是等于
   // 要画一个最简单的图，只有三个元素的数组
   // 初始 left = 1, right = 1(3-2) 此时不能退出，否则就没有值了 
   while(left <= right) {
    // 左右长板中找矮板
    let shortBoard = Math.min(leftMax, rightMax);
    // 左边更矮
    if(shortBoard == leftMax) {
      // 矮板比当前桶底还高，就可以盛水
      if(height[left] < shortBoard) {
        res += shortBoard - height[left];
      }
      // 更新新的左长板
      leftMax = Math.max(shortBoard, height[left]);
      left++;
    }
    // 右边更矮
    else if(shortBoard == rightMax){
      if(height[right] < shortBoard) {
        res += shortBoard - height[right];
      }
      rightMax = Math.max(shortBoard, height[right]);
      right--;
    }
   }
   return res;
   };

单调栈

var trap = function (height) {
  if (!height || height.length == 0) {
    return 0;
  }
  let stack = [];
  let res = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length != 0 && height[stack[stack.length - 1]] < height[i]) {
      let tmp = stack.pop();
      if (stack.length == 0) {  // 出栈以后，如果栈为空，说明不能形成凹槽，此时跳过即可
        break;
      }
      res += (Math.min(height[i], height[stack[stack.length - 1]]) -
        height[tmp]) * (i - stack[stack.length - 1] - 1);
    }
    stack.push(i);  // push的是下标
  }
  return res;
};

动态规划

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的**最大高度的最小值**，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。

朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n^2)
上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。

显然，leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：

• 当 1≤i≤n−1 时，leftMax[i] = max(leftMax[i−1], height[i])

• 当 0≤i≤n−2 时，rightMax[i] = max(rightMax[i+1], height[i])

因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。

在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。

动态规划做法可以由下图体现。

1. 往左边看的最大数组 max
2. 往右边看的最大数组 max

3. 动态规划 min

   1. 左右看去， 比较矮的那个减去当前盆子底部高度就行了 ```javascript var trap = function (height) { const len = height.length; if (len == 0) return 0;

   const leftMax = new Array(len).fill(0); leftMax[0] = height[0]; for (let i = 1; i < len; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); }

   const rightMax = new Array(len).fill(0); rightMax[len - 1] = height[len - 1]; for (let i = len - 2; i >= 0; —i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); }

   let ans = 0; for (let i = 0; i < len; ++i) { // 左右看去， 比较矮的那个减去当前盆子底部高度就行了 ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; }; ```