leetcode第11题，盛水最多的容器——双指针问题，O(n)时间复杂度解法！

题目描述

给你 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。

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

示例代码

时间复杂度为O ( n ) ，空间复杂度为O ( 1 )

class Solution {
    //这个题放在 在线测试还可以 放在面试中不太好描述吧
    public int maxArea(int[] height) {
    	int i = 0, j = height.length - 1;
    	int mm = 0;//用于存遍历过程中得到的存水最大值
    	while(true){
    		int m = (j-i)*(height[i] <= height[j]?height[i++]:height[j--]);
    		if(m > mm) mm = m;
    		if(i == j) break;
    	}
        return mm;
    }
}

思路解析

上面是一种双指针算法，指针 i 指向数组的开头，满足条件后只向后移动；指针 j 指向数组的末尾，满足条件后只向前移动。两指针相遇，算法结束。能使用这种算法解的题还有很多，在最后我还会举个例子。
那么指针移动的条件是什么呢？
在本题中指针移动的条件是，如果 a[i] <= a[j]，那么指针 i 则向后移动；如果 a[i] > a[j]，那么指针 j 则向前移动。
我们可以发现，虽然 i，j 指针合起来能遍历整个数组，但并没有穷举所有的容器情况。 例如，如果 a[i] <= a[j]，则 i++，排除了 a[i] 与 a[i+1,…,j-1] 之间的某个数构成最大盛水容器的可能性。

当a[i]后面的数都小于a[i]时，不可能存在能大于a[i]*a[j]的数，