计算机低能儿从0刷leetcode | 11.盛最多水的容器

题目：11. 盛最多水的容器

解答：

不想暴力遍历，于是让右端点j从最右侧开始遍历，每次寻找离j最远、且高度不小于height[j]的左端点i，结果发现错误，比如[1,2]的情况。

于是又打补丁，按同样思路左端点i从0开始遍历，每次寻找离i最远、且高度不小于height[i]的右端点j，结果正确，然而时间复杂度并没有比暴力遍历少。

class Solution {
public:
    int maxArea(vector<int>& height) {
    int maxarea=-1;
        int i=0,j=0;
        for(j=height.size()-1;j>=0;j--){    
            i=0;
            while (i<j&&height[i]<height[j]){
                i++;
            }
            int area=(j-i)*height[j];
            maxarea=max(maxarea,area);   
        } 

          for(i=0;i<height.size();i++){
            j=height.size()-1;
           while (j>i&&height[j]<height[i]){
                j--;
            }
            int area=(j-i)*height[i];
            maxarea=max(maxarea,area);   
        } 
        return maxarea;
    }
};

于是看了题解，使用双指针的方法，这里需要明确两个要点:

1、每次选择height[i]和height[j]中最小的那个，然后计算容量=(i-j) x 这个最小的高度。这一点很好理解。

2、关键在于，接下来i和j该如何移动。

如果选择将高度更大的指针向内移动，那么下一次计算min(height[i], height[j])的时候，这个最小值只会减小或不变，那么计算出的面积一定是在减小的（因为向内移动，宽度一定减小）。

如果选择将高度更小的指针向内移动，那么下一次计算min(height[i], height[j])的时候，这个最小值可能增大、可能减小。

因此我们得出结论：一定将高度更小的指针向内移动。代码如下：

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