Given a non-negative integer array representing the heights of a list of adjacent bars. Suppose each bar has a width of 1. Find the largest amount of water that can be trapped in the histogram.

Assumptions

• The given array is not null

Examples

• { 2, 1, 3, 2, 4 }, the amount of water can be trapped is 1 + 1 = 2 (at index 1, 1 unit of water can be trapped and index 3, 1 unit of water can be trapped)

Solution: 两指针往内扫，谁小移谁，并且记录左右高度，left > array[i]时，ans += left - array[i]，否则left = array[i]，同理right

    public int trapRainWater(int[] heights) {
        if(heights == null || heights.length <= 2){
            return 0;
        }
        int i = 0, j = heights.length - 1, ans = 0;
        int leftheight = heights[i], rightheight = heights[j];

        while(i < j){
            if(leftheight < rightheight){
                i++;
                if(leftheight > heights[i]){
                    ans += leftheight - heights[i];
                } else{
                    leftheight = heights[i];
                }
            } else{
                j--;
                if(rightheight > heights[j]){
                    ans += rightheight - heights[j];
                } else{
                    rightheight = heights[j];
                }
            }
        }
        return ans;
    }