42. Trapping Rain Water

source: https://leetcode.com/problems/trapping-rain-water/

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

暴力法

这一道题有几个最基础的概念：

• 某个index能接的雨水数量是其与，左右最大值之间的最小值，的差值。
• 最左和最右的位置肯定是接不住的

function trap(height: number[]): number {
    let ret = 0;
    const size = height.length;
    for (let i = 1; i < size - 1; i++) {
        let left = 0, right = 0;
        for (let j = i; j >= 0; j--) {
            left = Math.max(left, height[j]);
        }
        for (let j = i; j < size; j++) {
            right = Math.max(right, height[j]);
        }
        ret += Math.min(left, right) - height[i];
    }
    return ret;
};

但是这个版本的最大问题在于有许多的重复计算，每次左右的最大值都要从头算起。时间复杂度为O(n2), 空间复杂度为O(1).

从这个版本出发，所有优化都是围绕着如何最大利用已有计算结果。

动态规划

既然是利用已有计算结果，很明显，dp就浮现在脑海之中。

思路是：

1. 计算从左开始的最大值数组
2. 计算从右开始的最大值数组
3. 然后再迭代计算其差值

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let ret = 0;
  const size = height.length;
  if (!size) return ret;
  const leftMax = Array(size).fill(0);
  const rightMax = Array(size).fill(0);
  for (let i = 0; i < size; i++) {
    leftMax[i] = Math.max(
      leftMax[i - 1] === undefined ? -Infinity : leftMax[i - 1],
      height[i]
    );
  }
  for (let i = size - 1; i >= 0; i--) {
    rightMax[i] = Math.max(
      rightMax[i + 1] === undefined ? -Infinity : rightMax[i + 1],
      height[i]
    );
  }
  for (let i = 0; i < size; i++) {
    ret += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  return ret;
};

理论上，在这个方案中，是没有重复计算了的，时间复杂度O(n).

但是因为需要数组存储最大值，所以空间也是O(n).

双指针

和简单的双指针应用于排序后的数组不同，这里的双指针使用较为巧妙。

只有左右指针指向的值小于另外一个的时候，对应指针才会挪动。

这个规律对于这个数组带来一个很重要的属性：

• 因为只有小于才可以挪动，另外一个方向现在指向的值一定是大于所有这一方向已经遍历过的值的

据此，此时只用和此时方向的最大值比较差值就行。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let ret = 0;
  if (height.length < 3) return ret;
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      if (leftMax > height[left]) ret += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      if (rightMax > height[right]) ret += rightMax - height[right];
      right--;
    }
  }
  return ret;
};

时间复杂度O(n), 空间复杂度O(1).

总结

先总结基础规律，然后先给出暴力算法，再一步步的寻找优化途径。