LeetCode 42. 接雨水

接雨水

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

方法一、双指针解法

对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值，下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]。
记左边最大高度为：leftMax， 右边最大高度为：rightMax
则位置i处可储水容量：min(leftMax, rightMax) - height[i]

Swift

func trap(_ height: [Int]) -> Int {
        
        let cnt = height.count
        
        var ans = 0
        var left = 0, right = cnt-1
        
        var leftMax = 0
        var rightMax = 0
        
        while left < right {
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            
            if height[left] < height[right] {//height[left] < height[right]，必然有leftMax
                ans += leftMax - height[left]
                left += 1
            }else {
                ans += rightMax - height[right]
                right -= 1
            }
        }
        
        return ans
    }
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

OC

-(NSInteger)trap:(NSArray *)height {
    NSInteger ans = 0;
    
    NSInteger cnt = height.count;
    NSInteger left = 0, right = cnt - 1;
    NSInteger leftMax = 0, rightMax = 0;
    
    while (left < right) {
        leftMax = MAX(leftMax, [height[left] integerValue]);
        rightMax = MAX(rightMax, [height[right] integerValue]);
        
        if ([height[left] integerValue] < [height[right] integerValue]) {
            ans += leftMax - [height[left] integerValue];
            ++left;
        }else {
            ans += rightMax - [height[right] integerValue];
            --right;
        }
    }
    
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22