leetcode-42-Trapping-Rain-Water

发表于   |  

TOREVIEW

描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

img
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

分析

如图所示，求能够积攒多少雨水，对于每个坐标来说，收集的雨水等于左右两边的最大值中的较小值减去自己，然后遍历一遍累加即可，可以用两个数组来维护某节点的左边最大值和右边最大值。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxTmp = 0
        result = 0
        length = len(height)
        leftMax = [0] * length
        rightMax = [0] * length
        
        for i in range(length):
            maxTmp = max(height[i], maxTmp)
            leftMax[i] = maxTmp
        maxTmp = 0
        for i in range(length):
            maxTmp = max(height[length-i-1], maxTmp)
            rightMax[length-i-1] = maxTmp
            
        for i in range(length):
            result = result + (min(leftMax[i], rightMax[i])-height[i])
            
        return result

解决方案2(Javascript)

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
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let maxTmp = 0;
    let result = 0;
    const leftMax = [];
    const rightMax = [];
    
    for (let i = 0; i < height.length; i++) {
        maxTmp = Math.max(height[i], maxTmp);
        leftMax[i] = maxTmp;
    }
    maxTmp = 0;
    
    for (let i = height.length-1; i >= 0; i--) {
        maxTmp = Math.max(height[i], maxTmp);
        rightMax[i] = maxTmp;
    }
    
    for (let i = 0; i < height.length; i++) {
        result = result + (Math.min(leftMax[i], rightMax[i]) - height[i])
    }
    return result;
};

解决方案3（Golang）

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
func trap(height []int) int {
    length := len(height)
    if length == 0 {
        return 0
    }
    
    leftMax := make([]int, length)
    leftMax[0] = height[0]
    
    for i := 1; i < length; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }
    
    rightMax := make([]int, length)
    rightMax[length-1] = height[length-1]
    for i := length-2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }
    
    result := 0
    for i, h := range height {
        result += min(leftMax[i], rightMax[i]) - h
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相关问题

题目来源