【LeetCode-中等】11. 盛最多水的容器（详解）

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

题目地址：https://leetcode.cn/problems/container-with-most-water

示例

 解法1：双指针

思路

首先拿到这道题，先考虑到，这是一个算面积的题，面积=底边*高

所以，第一反应是想来个双层for爽一爽，也料到可能会超时

双层for

就是直接遍历这个数组，类似冒泡排序，将每两个数的面积 与 当前最大面积比较，如果比当前最大面积还大，那就更新当前最大面积，最后返回最大面积即可。

//暴力循环，超时
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i<height.length;i++){
            for (int j = i+1;j<height.length;j++){
                if ( (j-i) * min(height[i],height[j]) >max){
                    max = (j-i) * min(height[i],height[j]);
                }
            }
        }
        return max;
    }
    int min(int a,int b){
        return a<b ? a:b;
    }
}

结果就是超时。

想了一会儿，想不出来，看了题解，啊？双指针

双指针

就是在头和尾 分别放指针，将这两个指针之间的面积设置为当前最大面积，然后比较头尾指针的数据大小，将小的那个指针向中间移动，再与最当前最大面积比较，如果比当前最大面积大，就更新它，一直循环到两个指针相遇，返回最大即可。

如果是第一次做这个题，很难想到这个双指针的方法。

为什么 移动小的指针？

        因为在开头，我们将两个指针放在了头和尾，现在面积的底是最大的，而高度是取决于小的这个指针的，短指针已经限制了高度，如果移动高指针不可能增加整体的高度，而底在不断减少，所以移动短指针来尝试增加最大高度。

代码作者：jyd
链接：https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

效果

妙啊，妙啊

这个方法的核心是和双层for一样的，就是在找一个最大面积，而双指针减少了很多不必要的比较，时间复杂度上 优越些