LeetCode题解：42. 接雨水，栈，JavaScript，详细注释

[chencl1986]

原题连接：https://leetcode-cn.com/problems/trapping-rain-water/

解题思路：

1. 以该题的示例1为例，使用栈的解法，就是直观的去求所有柱子可装水的量。

2. 栈中存储的一直是水桶的左边界和桶底的索引，例如分别会存储索引[1, 2]、[3, 4, 5]、[7, 8, 9]。
3. 当遍历到柱子比栈顶高时，就将栈顶元素作为桶底出栈，出栈后剩下的栈顶即为左边界，以此形成水桶的一层，即可计算装水量，如下图：

4. 需要注意如果桶底元素出栈之后，栈为空，表示无法组成一个桶，例如桶底元素的索引是0，需要退出出栈循环。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let result = 0; // 储存总转水量
  let stack = []; // 栈中存储的是水桶的左边界和桶底

  // 遍历所有的柱子，在入栈之前，柱子都是作为水桶的右边界
  for (let right = 0; right < height.length; right++) {
    // 如果右边界比栈顶元素高，表示其与栈中元素形成了一个水桶，可以计算水桶的装水量
    while (height[right] > height[stack[stack.length - 1]]) {
      // 栈顶元素即为当前水桶的桶底，将其弹出并计算桶底高度
      const bucketBottom = height[stack.pop()];

      // 将桶底出栈之后，栈如果为空则表示不存在水桶，退出循环
      if (!stack.length) {
        break;
      }

      const left = stack[stack.length - 1]; // 剩余的栈顶元素为水桶的左边界，获取其索引
      const leftHeight = height[left]; // 获取水桶左边界的高度
      const rightHeight = height[right]; // 获取水桶右边界的高度
      const bucketTop = Math.min(leftHeight, rightHeight); // 水桶左右边界的较小值，即为桶顶高度
      const bucketHeight = bucketTop - bucketBottom; // 水桶的可装水高度为桶顶减去桶底高度
      const width = right - left - 1; // 水桶的实际宽度为左右边界之差减一
      const area = width * bucketHeight; // 计算当前水桶可装水量
      result += area; // 将水量加入总量
    }

    // 当前右边界可以作为下一个水桶的左边界，因此需要入栈
    stack.push(right);
  }

  return result;
};