Trapping Rain Water -- LeetCode

 
這道題比較直接的做法類似Longest Palindromic Substring中的第一種方法，對於每一個bar往兩邊掃描，找到它能承受的最大水量，然後累加起來即可。每次往兩邊掃的復雜度是O(n)，對於每個bar進行處理，所以復雜度是O(n^2)，空間復雜度是O(1)。思路比較清晰，就不列代碼了，有興趣的朋友可以實現一下哈。

下面我們說說優化的算法。這種方法是基於動態規劃的，基本思路就是維護一個長度為n的數組，進行兩次掃描，一次從左往右，一次從右往左。第一次掃描的時候維護對於每一個bar左邊最大的高度是多少，存入數組對應元素中，第二次掃描的時候維護右邊最大的高度，並且比較將左邊和右邊小的最大高度（我們成為瓶頸）存入數組對應元素中。這樣兩遍掃描之後就可以得到每一個bar能承受的最大水量，從而累加得出結果。這個方法只需要兩次掃描，所以時間復雜度是O(2*n)=O(n)。空間上需要一個長度為n的數組，復雜度是O(n)。代碼如下：

public int trap(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int max = 0;
    int res = 0;
    int[] container = new int[A.length];
    for(int i=0;i=0;i--)
    {
        container[i] = Math.min(max,container[i]);
        max = Math.max(max,A[i]);
        res += container[i]-A[i]>0?container[i]-A[i]:0;
    }    
    return res;
}