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

Have you met this question in a real interview?

Yes

Example

Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

思路

左右两边从小的出发，找到比小的那边大的第一个柱子， 小的决定水位

public class Solution {
    /*
     * @param heights: a list of integers
     * @return: a integer
     */
    //two pointer and find the first higher wall than itself
    public int trapRainWater(int[] heights) {
        // write your code here
        if (heights == null || heights.length < 3) {
            return 0;
        }
        int ans = 0;
        int i = 0; 
        int j = heights.length - 1;

        while (i < j) {
            int cur_i = heights[i];
            int cur_j = heights[j];

            if (cur_i < cur_j) {
                i++;
                while (heights[i] <= cur_i && i < j) {
                    ans += cur_i - heights[i];
                    i++;
                }
            } else {
                j--;
                while (heights[j] <= cur_j && i < j) {
                    ans += cur_j - heights[j];
                    j--;
                }
            }
        }
        return ans;
    }
}