接雨水 | 前端芯事

力扣 42: 接雨水

找思路：举两个位置为例子

不妨以官方示例的第一个数据为例，官方还提供了上方的图片

我们首先看最左边第 3 格接到了 1 格雨水的位置，因为其左侧的柱子高度为 1，右侧高度为 2，这个位置就能接 1 格雨水。

假设我们升高 1 格左侧的柱子到 2，我们容易得出结论，可以接 2 格雨水。

如果再升高至 3（仅看前 4 格），我们发现可以接雨水的格子不会再升高了，由此发现是由左右两侧的较低的柱子决定的。

我们可以再看一格，比如第 6 格的接 2 格雨水的位置，它的左侧最高高度是 2，右侧是 3，减去自身高度 0，所以它接了 2 格雨水。

实现

typescript

function trap(height: number[]): number {
  let leftMax = 0;
  let rightMax = 0;
  const lefts = [];
  const rights = [];
  
  for (let i=0; i<height.length; i++) {
    if (height[i] > leftMax) {
      leftMax = height[i];
    }
    lefts.push(leftMax);
  }
  
  for (let i=height.length-1; i>=0; i--) {
    if (height[i] > rightMax) {
      rightMax = height[i];
    }
    rights.unshift(rightMax);
  }
  
  let ans = 0;
  for (let i=1; i<height.length-1; i++) {
    ans += Math.min(lefts[i], rights[i]) - height[i];
  }
  
  return  ans;
};

上方代码，先把每个位置其左右两侧的最高值分别做了记录，然后再利用上方我们得到的基本思路，进行每个位置的计算。

322 个用例均通过了，但是执行用时在所有的提交中不算快，空间复杂度也较高。

优化

可以利用双指针去优化我们的算法，官方题解已经解释的很好了，图文并茂，所以我这里只写一下代码实现，具体可以顺着本文最早给出的链接去看官方题解。

唯一可以多说的是，这里的双指针移动的策略，非常像另外一题，盛水最多的容器，我们会优先移动较短的那个指针。

而且，因为移动的那个指针肯定是较小的，所以不需要和右指针比较，直接减去当前位置的柱子高度即可。

typescript

function trap(height: number[]): number {
  let leftMax = 0;
  let rightMax = 0;
  let left = 0;
  let right = height.length - 1;
  let ans = 0;
  
  while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    
    if (height[left] < height[right]) {
      ans += leftMax - height[left] ;
      left++;
    } else {
      ans += rightMax - height[right];
      right--;
    }
  }
  
  return ans;
};

提交后，发现执行用时已经算是前 10% 了，空间复杂度也有很大的提升。

找思路：举两个位置为例子 ​

实现 ​

优化 ​

找思路：举两个位置为例子

实现

优化