学步园

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.

思路：假设对于数组中第i个数字，判断A[i]是否小于左侧最大的数，并且小于右侧最大的数。刚开始我是这么考虑的，从当前位置i，向左搜索找到大于A[i]的最大的数，位置为j，然后从i向右搜索，找到大于A[i]的最大的数，位置为k。然后存储的水量为(k-j-1)*min(A[k],A[j])-{A[j+1]...A[k-1]之和}。但是这种想法有种情况未考虑，例如[5,4,1,2]真正存储的水的j=1,i=2,k=3，并不是上面想法的j=0,i=2,k=3。所以需要对上述解法需要加入限定，例如先获得i=2的左侧最大值为5，i=2的右侧最大值为2，取得key=min(5,2)=2，然后再从i=2向左搜索，一旦有数>=key，则位置为j,同理，右侧位置为k。ok，AC了！

class Solution {
public:
    int min(int a, int b)
    {
        return a<=b ? a:b;
    }    
    int trap(int A[], int n) {
        int i,leftH[n],rightH[n],j,k,key;
        int trapWater = 0,extra;
        if(n==0 || n==1 || n==2)
        {
            return trapWater;            
        } 
        int left = INT_MIN, right = INT_MIN;
        for(i=0; i<n; ++i)
        {
            leftH[i] = left;
            if(left < A[i])
            {
                left = A[i];
            }    
        }       
        for(i=n-1; i>=0; --i)
        {
            rightH[i] = right;
            if(right < A[i])
            {
                right = A[i];
            }     
        }  
        
        for(i=0; i<n; ++i)
        {
            if(A[i] < leftH[i] && A[i] < rightH[i])
            {
                key = min(leftH[i],rightH[i]);
                j = i - 1, k = i + 1;
                extra = A[i];
                while(j>=0 && A[j] < key)
                {
                    extra += A[j];
                    --j;
                }    
                while(k<n && A[k] < key)
                {
                    extra += A[k];
                    ++k;
                }   
                trapWater += ((k-j-1)*key-extra);
                i = k;
            }      
        }    
        return trapWater;  
    }
};