11. Container With Most Water

容器短板问题
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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 and n is at least 2.

---

大致意思：给定n个非负整数a1,a2,...,an，每一个整数代表一个坐标点。以此点做关于x轴的垂线，这样会有n条垂直于坐标轴的垂线，其中任意两条线可以构成一个容器，找到这样的两

条线构成的容器能够装尽可能多的水。

注意：其中n至少为2，也就是说至少存在一个容器。

提示：首先需要明白一点，两条线组成的容器，能够容纳的水量是最短的那根线决定。可以看下图辅助理解。

容器图

常规解法：我们可以将a1和an这两条边界线组成的容器作为初始容器，先求出两根线中的最短的线做为高，记容器高H=min(a1,an)，记容器的长L=(n-1)，初始容器体积为V=L*H。计算容器容积时要考虑到长的因素，以H为高的其他任何容器都不会比初始容器体积大，因为其他容器的高（最短的线）最大为H，而长必定小于L，所以a1和an中小的那条线在后续比较中就可以不考虑了。如果H==a1，说明a1是最小的，肯定小于初始容器体积，我们继续看a2和an组成的容器，否则查看a1和an-1组成的容器，同时更新最大容器值。依照这样的策略逐步缩小范围，最终就得到了最大容器。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int maxa=0,i=0,j=n-1;
        while(i<j)
        {
            maxa=max(maxa,min(height[i],height[j])*(j-i));
            if(height[i]>height[j])
                --j;
            else
                ++i;
        }
        return maxa;
    }
};