42.接雨水

2020-04-17

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，

计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，

在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

题解:

思路1：记录每一个下标左右最大值

 

var trap = function (height) {
  let leftMax = 0, rightMax = 0;
  let LMArr = [], RMArr = [];
  let sum = 0;
  for (let i = 0; i < height.length; i++) { // 第一个遍历找到height每一项对应的左边的最大值 
    leftMax = Math.max(height[i], leftMax);
    LMArr.push(leftMax); // height[i]左边的最大值=LMArr[i]
  }

  for (let i = height.length - 1; i >= 0; i--) { // 第二个遍历找到height每一项对应的右边的最大值 
    rightMax = Math.max(height[i], rightMax);
    RMArr.unshift(rightMax); // height[i]右边的最大值=LMArr[i]
  }

  for (let i = 0; i < height.length; i++) { // 第三个遍历判断每一项能装但是水
    let tmp = Math.min(LMArr[i], RMArr[i]);
    if (height[i] < tmp) sum += tmp - height[i];
  }

  return sum;
}

思路2：双指针

 

var trap = function (height) {
  let leftMax = 0; // 记录左边界的最大值
  let rightMax = 0; // 记录右边界的最大值
  let l = 0, r = height.length - 1; // 左右指针
  let sum = 0; // 总共的水
  while (l < r) {
    // 如果左指针的值小于右指针的值 则左指针的值必定小于右边界 此时只需要判断左指针的值跟左边界的差值
    if (height[l] < height[r]) {
      // 判断左指针的值和左边界最大值的大小 如果左边界大 那么可以蓄水 如果左指针的值大
      // 不能蓄水 更新左边界的最大值
      height[l] > leftMax ? (leftMax = height[l]) : sum += (leftMax - height[l]);
      l++;
    } else { // 同样的 如果右指针的值小于左指针的值 那么右指针的值必定小于左边界 此时只需判断右指针和右边界的差值
      // 判断右指针的值和右边界最大值的大小 如果右边界大 那么可以蓄水 如果右指针的值大
      // 不能蓄水 更新右边界的最大值
      height[r] > rightMax ? (rightMax = height[r]) : sum += (rightMax - height[r]);
      r--;
    }
  }
  return sum;
};