1. 题目描述

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

示例 1：
rainwatertrap.png

  1. 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出：6
  3. 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

  1. 输入：height = [4,2,0,3,2,5]
  2. 输出：9

提示：

  • n == height.length
  • 0 <= n <= 3 * 104

  • 0 <= height[i] <= 105

    2. 解题思路

    看到这道题，我们自然而然的可以想到木桶效应，每根柱子上的雨水的深度取决于它两侧最高的柱子中较短的那根柱子的长度。

  • 如果这个较短的柱子的长度大于当前柱子，那么雨水的深度就是较短的柱子减去当前柱子的长度；

  • 如果这个较短的柱子的长度小于等于当前柱子，那么雨水的深度就是0。

复杂度分析：

  • 时间复杂度：O(n2) ，数组中每个元素都需要向左右扫描
  • 空间复杂度：O(1)

    3. 代码实现

    1. /**
    2. * @param {number[]} height
    3. * @return {number}
    4. */
    5. var trap = function(height) {
    6.   let len = height.length, sum = 0
    7.   for(let i = 0; i < len - 1; i++){
    8.       // 计算当前柱子左侧的最大值
    9.       let left = 0
    10.       for(let j = i - 1; j >= 0; j--){
    11.           left = height[j] >= left ? height[j] : left
    12.       }
    13.       // 计算当前柱子右侧的最大值
    14.       let right = 0
    15.       for(let j = i + 1; j < len; j++){
    16.           right = height[j] >= right ? height[j] : right
    17.       }
    18.       // 计算当前柱子能接的雨水量
    19.       if(min > height[i]){
    20.           sum += Math.min(left, right) - height[i]
    21.       }
    22.   }
    23.   return sum
    24. };

    4. 提交结果

    image.png