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.

[圖片上傳失敗...(image-91728e-1513831694434)]
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

一刷
題解：

1. 像Container with most water一樣堂湖，設(shè)立一個lo = 0闲先， hi = height.length - 1，使用雙指針來夾逼遍歷无蜂。
2. 設(shè)立一個res = 0伺糠， maxLeftBar = 0, maxRightBar = 0
3. 在 lo <= hi的條件下進(jìn)行遍歷
   1. 假如height[lo] <= height[hi]，或者h(yuǎn)eight[lo] < height[hi]也可以斥季， 這時候說明當(dāng)前左邊的height <= 右邊的height训桶。那么我們只需要考慮左邊界和當(dāng)前左邊的height的差值，這個差值就是我們能容納多少水

1. 在上述情況下酣倾，假如height[lo] >= maxLeftBar舵揭， 當(dāng)前index的值 > maxLeftBar，那么我們不能接到水躁锡，我們要把maxLeftBar更新為height[lo]
2. 否則res += maxLeftBar - height[lo]午绳，我們把這個差值加入到結(jié)果中
3. lo++
   2. 否則，左邊的當(dāng)前height > 右邊的當(dāng)前height映之，容易能盛多少水取決于右邊的height以及maxRightBar的差值
4. 當(dāng)height[hi] >= maxRightBar,我們更新maxRightBar = height[hi]
5. 否則拦焚，我們把結(jié)果 maxRightBar - height[hi]加入到res中
6. hi--

4. 最后返回結(jié)果res就可以了蜡坊， 很巧妙。

Time Complexity - O(n)耕漱， Space Complexity - O(1)
還有stack 和dynamic programming的方法留給二刷三刷

public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int lo = 0, hi = height.length-1;
        int maxLeftBar = 0, maxRightBar = 0;
        int res = 0;
        while(lo<=hi){
            if(height[lo] <=height[hi]){
                if(height[lo] >=maxLeftBar) maxLeftBar = height[lo];
                else res += maxLeftBar - height[lo];
                lo++;
            }
            else{
               if(height[hi] >=maxRightBar) maxRightBar = height[hi];
                else res += maxRightBar - height[hi];
                hi--; 
            }
        }
        
        return res;
    }
}

二刷思路同上

class Solution {
    public int trap(int[] A) {
        int res = 0;
        int left = 0, right = A.length-1;
        int maxLeft = 0, maxRight = 0;
        while(left<=right){
            if(A[left]<A[right]){//regard the right as wall
                if(maxLeft<A[left]) maxLeft = A[left];
                else res += maxLeft -A[left];
                left++;
            }else{
                if(maxRight<A[right]) maxRight = A[right];
                else res += maxRight -A[right];
                right--;
            }
        }
        return res;
    }
}