42.md

Leetcode 42. 接雨水

42. 接雨水

const trap = function (height) {
  const n = height.length;
  if (n == 0) {
    return 0;
  }

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


  // 创建长度为 n 的数组 leftMax， 0 <= i，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度。

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

  console.log(leftMax);

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

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

  // 在得到数组 leftMax 和 rightMax 的每个元素值之后，下标 i 处能接的雨水量等于 Math.min(leftMax[i], rightMax[i]) - height[i]，遍历每个下标即可得到总的接水量

  let ans = 0;
  for (let i = 0; i < n; i++) {
    console.log(i, Math.min(leftMax[i], rightMax[i]) - height[i]);
    ans = ans + Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return ans;
}

const height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log(trap(height));