盛最多水容器

要求

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

示例

输入: [1,8,6,2,5,4,8,3,7]

输出: 49

代码

• 暴力法：在所有可能性中选择符合要求的

int maxArea(vector<int>& height) {
    int max = 0,i,j,v,h;
    int n = height.size();
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            h = height[i]>height[j]?height[j]:height[i];
            v = h*(j-i);
            max = v>max?v:max;
        }
    }
    return max;
}

• 双指针法

	int maxArea(vector<int>& height) {
    int max=0,i=0,j,v;
    j = height.size()-1;  //最后一个元素的位置应该在个数减1.
    while(i<j)
    {
        int h = height[i]<height[j]?height[i]:height[j];
        v = h*(j-i);
        max = max>v?max:v;
        if(height[i]<height[j]) i++;   //朝边较短的一向移动
        else j--; 
    }
    return max;
	}

评价

• 此题就是个数学问题。矩形区域的面积是取决于较短的那一条边的，所有在把矩形向中间压缩的过程中，底是变短的，所有只能移动较短的一条边，才有可能形成底变短，高变长，最后面积变大的情况。