42. 接雨水

题目描述

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

输入输出

1
2
3
4
5
6
输入：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 个单位的雨水（蓝色部分表示雨水）。 

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

基本思路

和这道题有些类似：11. 盛最多水的容器

对于下标i 下雨后水能到达的最大高度等于下标i两边的最大高度的最小值

下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]

leftMax表示当前在height[left]中及其左边 height的最大高度 rightMax是右边的最大高度

  • 若height[left] < height[right] 则必有leftMax < rightMax 下标left出所能接的雨水量等于leftMax - height[left] 增加到res中 然后left右移
  • 若height[left] > height[right] 则必有leftMax > rightMax 下标right出所能接的雨水量等于rightMax - height[right] 增加到res中 然后right右移

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int res = 0;
        while(left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if(height[left] < height[right]){
                res += leftMax - height[left];
                left++;
            }
            else{
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}