id 11. Container With Most Water Add to List QuestionEditorial Solution My Submissions
Total Accepted: 105561
Total Submissions: 293689
Difficulty: Medium
Contributors: Admin
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.

题目意思，假设一个二维的平面上有x和y轴，数组里面的数构成了在平面上的坐标，比如height[i]的的坐标就是(i,height[i]),将其(i,0)和(i,height[i])连线，构成一个线，现在找两个这种线，让其往里倒水可以盛最多的水。

note:

水的体积应该由最短的线决定。如图

穷举

在一开始我们可以使用暴力穷举的方法进行

#include <iostream>
#include <string>
#include<vector>
using namespace std;
//动态规划 超时
class Solution {
public:
    int maxArea(vector<int>& height) {
        int result=0;
        int area;
        for(int i=0;i<height.size();i++)
        for(int j=i+1;j<height.size();j++)
        { if(height[i]<=height[j])
             area=(j-i)*height[i];
             else
             area=(j-i)*height[j];
             if (area>result)
             result=area;
            }
        return result;
    }
};
int main()
{  vector<int> height= {1,2,5,6,9,8,96,5,4,5,23,6,57,85,9};
  Solution s;
  cout<<s.maxArea(height);
}

但是这么做可想而知是会超时的，因为涉及非常多的重复计算。

方法二

我们使用双指针向两边靠拢的方式进行遍历

其中面积是由

$$S\left( i,j \right) =\min \left( height\left( i \right) ,height\left( j \right) \right) *\left( j-i \right)$$
决定的，所以在由两边向中间靠拢的时候，一定有
$$\left( j’-i’ \right) <\left( j-i \right)$$
所以这个面积公式决定性的部分只有考虑
$$\min \left( height\left( i \right) ,height\left( j \right) \right) $$
部分

考虑情况

当 $height(i) < height(j)$ 时，对任何 $j’<j$ 来说一定有：

(a) $min(height(i),height(j’))<height(i)=min(height(i),height(j))$
所以让 $j’$ 继续移动是没有意义的,从而排除了以i为左边界的情况。所以需要执行i++;

2 . $height(i) > height(j)$ 需要j–;

$height(i) =height(j)$ 需要 i++,j–;

note:
左右边界的长度在更新的过程总是递增的！有助于理解。
所以代码如下：

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