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.

我觉得这道题和买股票以及最大储水量的题目很相似，感觉应该用divide-and-conquer的方法做

但是不是。。。这是别人给出的答案

想法太巧妙。。。啊。。。。

An O(n) solution is to consider each bar at a time, we can see that, for each bar, the water itself can trap depends on the max height on its left and right, e.g.  if current bar is of height 2, the max height on its left is 4, max height on its right is 3,   then water can be trapped in this bar is min(4,3)-2 = 1.

Thus, we can scan the whole map twice to get the max height on right and left, respectively. Finally scan the map again to get the water trapped of all.

public class Solution {    public int trap(int[] A) {                if(A.length == 0 || A.length == 1) return 0;                int[] l = new int[A.length];        int[] r = new int[A.length];                l[0] = 0;        for(int i = 1; i < A.length; i++)        {            l[i] = Math.max(A[i-1], l[i-1]);        }                r[A.length-1] = 0;        for(int i = A.length -2; i >= 0; i--)        {            r[i] = Math.max(A[i+1], r[i+1]);        }                int sum = 0;        for (int i = 0;i < A.length;i++)        {            if (Math.min(l[i],r[i])-A[i] >0 )            {                sum += Math.min(l[i],r[i])-A[i];            }        }                return sum;    }}

Trapping Rain Water