Leetcode - 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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.


[分析] 此题两种解法均参考http://blog.csdn.net/linhuanmars/article/details/20888505，详细分析可查看原文。摘出关键点拨：思路 1 从两边各扫描一次得到我们需要维护的变量，通常适用于当前元素需要两边元素来决定的问题，非常类似的题目是Candy， 思路2 是向中间夹逼时能确定接下来移动一侧窗口不可能使结果变得更好，所以每次能确定移动一侧指针，直到相遇为止。这种方法带有一些贪心，用到的有Two Sum，Container With Most Water。

public class Solution {
    // method 1: time O(N), space O(N), need 2 scans
    public int trap(int[] height) {
        if (height == null || height.length <= 2)
            return 0;
        int N = height.length;
        int[] bar = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            bar[i] = max;
            max = Math.max(max, height[i]);
        }
        max = 0;
        int res = 0;
        for (int i = N - 1; i >= 0; i--) {
            bar[i] = Math.min(max, bar[i]);
            max = Math.max(max, height[i]);
            res += bar[i] - height[i] > 0 ? bar[i] - height[i] : 0;
        }
        return res;
    }
    // method 2: time O(N), only one scan
    public int trap2(int[] height) {
        if (height == null || height.length <= 2)
            return 0;
        int l = 0, r = height.length - 1;
        int min;
        int res = 0;
        while (l < r) {
            min = Math.min(height[l], height[r]);
            if (height[l] == min) {
                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;
    }
}