学步园

Given n non-negative integers a₁, a₂,
..., a_n,
where each represents a point at coordinate (i, a_i). n vertical
lines are drawn such that the two endpoints of line i is at (i, a_i)
and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

意思就是选两个数字来组成一个容器，问最多可以得到多少水。其实也就是求最大面积。

面积取决于两个要素：长和高，很明显我们从两头开始向中间逼近的时候，长是在减小的，所以为了面积增加，必须高要增加，对吧。

然后两端的高度的较小值跟高度乘积就是当前面积。而两头都可以向中间逼近以获得更大的高度，但每次逼近应当选取较小的那一端。

class Solution {
public:
    int maxArea(vector<int> &h) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    int n=h.size();
	if ( n <=1 )
		return 0;

	int ans=0;

	int l=0,r=n-1;
	while(l<r)
	{
		ans= max(ans,(r-l)*min(h[l],h[r]));
		if ( h[l] < h[r] )
		{
			int preL=h[l];
			while(l<r && h[l]<=preL)
				l++;
		}
		else
		{
			int preR=h[r];
			while(l<r&&h[r]<=preR)
				r--;
		}	
	}
	return ans;
    }
};

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!

题意比较好理解，如果我们从全局上来考虑，去思考会形成多少个坑，然后计算每个坑能装多少水，就会比较麻烦。

简单的思路是：每个坐标位置是否能装水，能装多少水，这个是很容易计算的，最后全部加起来就好了嘛。

那么一个坐标位置能不能装水呢？条件是左右两遍都有比它高的柱子，那么肯定能形成一个坑，然后能装多少水呢？当然是由左右两个高柱子低的那根与自己高度的差值了。配合上面配图，应该比较好理解的。

所以问题转变为，求每个位置，左右最高的高度是多少：

class Solution {
public:
    int trap(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        assert(A&&n>=0);
	    if ( n<=2 ) 
		    return 0;
	    vector<int> lHigh(n,0);
	    int leftH=0;
	    for(int i=0;i<n;i++)
	    {
		    lHigh[i]=leftH;
		    leftH=max(leftH,A[i]);
	    }
	    int ans=0;
	    int rightH=0;
	    for(int i=n-1;i>=0;i--)
	    {
		    int h=min(rightH,lHigh[i]);
		    if ( h>A[i] )
			    ans+=h-A[i];
		    rightH=max(rightH,A[i]);
	    }
	    return ans;
    }
};