LeetCode42----接雨水

发表于 | 更新于: | 阅读次数:

问题

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

image.png

示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

解法

雨水的量 = 蓝色的面积+黑色的面积 - 黑色的面积

image.png

  • 首先可以知道从左后最高点位置，柱体（蓝+黑）是越来越高的，最右到最高点位置也是。
  • 使用 cur 记录当前的高度
  • 从左到最高点位置，如果当前高度没有高于 cur ,就不用更新cur, 否则就更新 cur .
  • 总的面积就是每个柱形的面积和，即每次遍历的时候就 加上 cur.
  • 加上最高的位置的大小 hegiht[maxIndex]
  • cur 更新为 0 再从右到最高点以同样的方式记录。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        
        int maxIndex = 0;
        for(int i= 0 ; i< height.length ;i++){
            if(height[maxIndex] < height[i]){
                maxIndex = i;
            }
        }
        int cur =0;
        int sum = 0;
        
        for(int i=0;i<maxIndex ;i++){
            if(height[i] > cur){
                cur = height[i];
            }
            sum += cur;
        }
        
        sum += height[maxIndex];
        
        cur = 0;
        for(int i = height.length -1;i > maxIndex ;i--){
            if(height[i] > cur){
                cur = height[i];
            }
            sum += cur;
        }
        
        for(int i=0;i< height.length ;i++){
            sum-=height[i];
        }
        return sum;
        
        
    }
}
0%