42. 接雨水

难度: 困难

来源: 每日一题 2023.07.23

---

给定 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

class Solution {
    public int trap(int[] height) {

    }
}

分析与题解

---

• 动态规划

  这个题目自己白天看的时候是没有任何的具体的思路, 主要是想到了木桶效应, 再就没有任何思路了.... 晚上看了题解,然后自己做出来了,主要思路是这样的.

  核心思路就是木桶效应, 判断 下标i 点是否有水,需要满足一下几个条件

  • i 不能是 0 或者 length - 1 的点.

  • 寻找 i 左右最高两个点 leftMax 和 rightMax 都要比 i 高.

  • 雨水量就是 左右最高两个点 leftMax 和 rightMax 的 较小值 - i点的值, 也就是木桶效应的体现....

  所以我们需要做一下几点工作.

  • 寻找 i 点的左右最高两个点 leftMax 和 rightMax, 我们可以用 leftMax[i] 和 rightMax[i] 存储 i点 的左右两边最高值,逻辑代码如下所示. 这个状态转移方程还是比较简单的, 但是简单的我也不会.......

    int length = height.length;
    int[] leftMax = new int[length];
    int[] rightMax = new int[length];
    for(int i = 1; i < length - 1; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
    }
    for(int i = length - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
    }
    

  • 根据木桶效应,比较 下标i 的存雨量. 同时添加到总量中.

    int sum = 0;
    
    // 其他逻辑代码
    ...
    
    for(int i = 1; i < length-1; i++) {
        int min = Math.min(rightMax[i], leftMax[i]);
        if (min > height[i]) {
            sum = sum + (min - height[i]);
        } 
    }        
    
    

  整体逻辑代码如下所示.

  class Solution {
      public int trap(int[] height) {
          // 动态规划, 求出当i时,左右的最高点
          int sum = 0;
          int length = height.length;
          int[] leftMax = new int[length];
          int[] rightMax = new int[length];
          for(int i = 1; i < length - 1; i++) {
              leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
          }
          for(int i = length - 2; i >= 0; i--) {
              rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
          }
          for(int i = 1; i < length-1; i++) {
              int min = Math.min(rightMax[i], leftMax[i]);
              if (min > height[i]) {
                  sum = sum + (min - height[i]);
              } 
          }
          return sum;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 三次遍历循环, 时间复杂度与 height 的长度成线性关系.
  • 空间复杂度: O(n), 两个状态转移方程的长度与 height 的长度成线性关系.

  结果如下所示.