742.接雨水

42.接雨水

Category	Difficulty	Likes	Dislikes
algorithms	Hard (62.37%)	4118	-

Tags
Companies
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

---

Discussion | Solution

思路

定义了一个函数 getMax，它接受两个参数 direction 和 index，返回一个数字类型的值。getMax 函数的作用是获取 height 数组中从 index 到数组末尾或从数组开头到 index 的最大值。
然后使用一个 for 循环遍历 height 数组。每次循环都会调用 getMax 函数获取当前位置左右两侧的最大值，并将其分别赋值给 leftMax 和 rightMax。然后获取当前位置的高度，赋值给 curHeight。
接下来的 if 语句用于判断当前位置是否可以进行接雨水操作。如果当前位置左侧或右侧没有比当前位置更高的位置，则无法接雨水，直接进入下一次循环。
如果当前位置可以进行接雨水操作，则计算出左右两侧最大值中较小的一个，并减去当前位置的高度，得到当前位置可以接到的雨水的高度，并将其加入到 res 中。

解答

/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let res = 0;

  const getMax = (direction, index) => {
    return Math.max(
      ...(direction ? height.slice(index) : height.slice(0, index))
    );
  };

  for (let i = 0; i < height.length; i++) {
    const leftMax = getMax(false, i),
      rightMax = getMax(true, i);
    const curHeight = height[i];
    if (leftMax === -Infinity || rightMax === -Infinity) continue;
    if (curHeight >= leftMax || curHeight >= rightMax) continue;
    const maxHeight = Math.min(leftMax, rightMax);
    res += maxHeight - curHeight;
  }

  return res;
};
// @lc code=end