每日算法之三十三：Trapping Rain Water

这是一个很有意思的问题，求解最大容积问题，值得动脑筋想一想。

原题如下：

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.

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!

<span style="font-size:18px;">class Solution {
public:
    int max_value(int a,int b)
{
	return a>b?a:b;
}
int max_element_position(int A[],int begin,int end)
{
	int max =	A[begin];
	int pos = begin;
	for(int i = begin+1;i<=end;i++)
		if(A[i]>max)
		{
			max = A[i];
			pos = i;
		}
	return pos;
}
int water(int A[],int start,int left_max,int end,int right_max)
    {
      int left = 0,right = 0,mid = 0;
      if(start == end)
      {
        if(left_max>A[start] && right_max>A[start])
          return min(left_max,right_max) - A[start];
        else
          return 0;
      }
      int max = max_element_position(A,start,end);
	  if(A[max]<left_max && A[max]<right_max)//这里要注意，中间的最大值也可能上面存储水
	  {
		  mid = min(left_max,right_max) - A[max];
	  }
      
      if(max-1 >= start)
        left = water(A,start,left_max,max-1,max_value(right_max,A[max]));
      if(max+1 <= end)
        right = water(A,max+1,max_value(left_max,A[max]),end,right_max);
      return left+right+mid;
    }
    int trap(int A[], int n) {
        if(n<=2)
          return 0;
        return water(A,0,0,n-1,0);
    }
};</span>

int trap(int A[], int n) {
        // Note: The Solution object is instantiated only once.
        if(A==NULL || n<1)return 0;
    	
		int maxheight = 0;
		vector<int> leftMostHeight(n);
		for(int i =0; i<n;i++)
		{
			leftMostHeight[i]=maxheight;
			maxheight = maxheight > A[i] ? maxheight : A[i];
		}

		maxheight = 0;
		vector<int> rightMostHeight(n);
		for(int i =n-1;i>=0;i--)
		{
			rightMostHeight[i] = maxheight;
			maxheight = maxheight > A[i] ? maxheight : A[i];
		}

		int water = 0;
		for(int i =0; i < n; i++)
		{
			int high = min(leftMostHeight[i],rightMostHeight[i])-A[i];
			if(high>0)
				water += high;
		}
		return water;
    }

每日算法之三十三：Trapping Rain Water,,5-wow.com