LeeCode 42.接雨水

发表于 | 分类于
字数统计: 714 | 阅读时长 ≈ 3

LeeCode 【42.接雨水】

题目描述 ：

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

示例

  • 输入： [0,1,0,2,1,0,1,3,2,1,2,1]
  • 输出：6

思路 1

使用逼近的思想，左右两个指针，分别指向首个元素、末尾元素。比较两个元素的大小，赋值于min，然后判断l、r位置的元素哪个是这个min，如果是height[l], 则继续用其相邻元素和其比较，如果小于它，则两者之差就是所要求的雨水的柱子。另外的heihgt[r]和它类似。

代码 1

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
class Solution {
    public int trap(int[] height) {
      int len = height.length;
        int l = 0;
        int r = len - 1;
        int res = 0;
        while (l < r) {
            int min = Math.min(height[l],height[r]);
            if(min == height[l]) {
                l ++;
                while(l < r && height[l] <= min) {
                    res += (min - height[l]);
                    l ++;
                }
            }else {
                r --;
                while(l < r && height[r] <= min) {
                    res += (min - height[r]);
                    r --;
                }
            }
        }
        return res;
    }
}

思路 2

上面的思路只需要遍历依次即可，而这个需要遍历两次，第一次需要从左到右求出相邻元素的最大边界值，这是向左看齐的，得出left数组。第二次需要从右向左求出相邻元素的最大值，这是向右看齐的，得出right数组。最后再遍历一次height数组，比较相同位置的left和right，取较小的值减去相应的height值，即可得出该位置可以蓄水的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int trap(int[] height) {
      int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int flag = 0;
        for(int i = 0; i < len; i ++) {
            flag = Math.max(flag, height[i]);
            left[i] = flag;
        }
        flag = 0;
        for(int i = len - 1; i >= 0; i --) {
            flag = Math.max(flag, height[i]);
            right[i] = flag;
        }
        int res = 0;
        for(int i = 0; i < len; i ++) {
            res +=(Math.min(left[i], right[i]) - height[i]);
        }
        return res;
    }
}

完整代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package nod1995;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * Created by 张超帅 on 2018/11/25.
 */
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int l = 0, r = len - 1;
        int res = 0;
        while(l < r) {
            int min = Math.min(height[l], height[r]);
            if(min == height[l]) {
                l ++;
                while(l < r && height[l] < min) {
                    res +=(min - height[l]);
                    l ++;
                }
            }else {
                r --;
                while(l < r && height[r] < min) {
                    res +=(min - height[r]);
                    r --;
                }
            }
        }
        return res;
    }
}
public class Main {
    public static int[] StringToInteger(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if(input == null) {
            return new int[0];
        }
        String[] parts = input.split(",");
        int[] result = new int[parts.length];
        for(int i = 0; i < parts.length; i ++) {
            result[i] = Integer.parseInt(parts[i].trim());
        }
        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line = null;
        while((line = in.readLine()) != null) {
            int[] height = StringToInteger(line);
            int ret = new Solution().trap(height);
            System.out.println(String.valueOf(ret));
        }
    }
}