11. Container with most water: 只是找到最大的那个可能

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, res = 0;
        while (left < right) {
            res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) left++;
            else right--;
        }
        return res;
    }
}

42. Trapping rain water: 从左到右每一个都要加

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.

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