LeetCode刷题笔记-11. 盛最多水的容器

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

说明：你不能倾斜容器，且 n 的值至少为 2。

示例：

输入：[1,8,6,2,5,4,8,3,7] 输出：49

题解：
这道题首先很轻易地就可以想出暴力法：遍历所有的两端点i，j情况，然后找出最大的water=（j-i）*min（h[j],h[i]），代码如下：

class Solution {
    public int maxArea(int[] height) {
        int n=height.length;
        int water;
        int result=0;
        int high;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                high=Math.min(height[i],height[j]);
                water=(j-i)*high;
                if(water>result){
                    result=water;
                }
            }
        }
        return result;
    }
}

暴力法的时间复杂度为O（n²）。
我们可以考虑双指针法：
我们在由线段长度构成的数组h中使用两个指针，一个left放在开始，一个right置于末尾。给定一个water的初始值，此时h[left]和h[right]有可能一大一小（我们姑且认为左长），也可能长度相同，接下来有两种操作可以选择：

• 右移left，因为right处的高度较小，决定了high的高度，而right-left的值-1，所以此时water=high*（right-left）一定会减小。甚至如果right一直不动的话，一直右移left到末尾也不会再找到比初始water更大的数。所以移动长边不会找到更大的water值
• 左移right，此时water有可能增大有可能减小，但比起毫无希望的移动长边，移动短边起码有可能找到更大的值。

一直向中心位置移动短边，记录每次求得的water，如果比max_water大即更新，直到left==right， max_water就是最终结果。
不理解的话我们换一种思路
其实我们也用到了暴力法的思想，只是把很多不可能符合要求的结果剃枝了。还是回到初始情况，我们选择把left固定 right从最右端向左遍历，如果right初始比较长的话，一直遍历到最后也不会再找到比初始water更大的数，我们不把他写到程序里是因为我们知道在移动的是长边时不可能找到更大的water。如果right初始较短，则有可能找到更大water，但是一旦right比left还长却要继续移动时，我们就应该明白接下来的移动其实是是指浪费时间，不如直接移动left进入到下一个遍历中（此时要移动的left是短边），总结规律就是短边向中心移动，直到left= =right。此时最大的water就是最终结果。
代码如下：

class Solution {
    public int maxArea(int[] height) {
        int n=height.length;
        int water;        
        int result=0;
        int left=0,right=n-1;
        while(left!=right){
            water=(right-left)*Math.min(height[left],height[right]);
            if(height[left]>=height[right]) right--;
            else left++;
            if(water>=result) result=water;
        }
        return result;
    }
}

时间复杂度降到了O(N)，nice！
大神题解