算法-盛最多水的容器（双指针法）详解程序员

力扣（LeetCode）连接 盛最多水的容器

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

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

解体思路:
双指针从两边向中间运算，比较左右两个容器壁大小，让一方小的主动向另外一方靠近（因容器盛水量大小受小的一方影响，如果挪动大的，加上两壁距离-1，这样只会让盛水量更小），直到两者相等（循环条件）；

示例：

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

下面是自己实现的几种方式比较，还请大佬勿喷；有更好的思路还请指点评论留言

实现方式一：（暴力解题法，缺点时间复杂度n^2，效率较低）

	public static int maxArea(int[] height) {
    
		int maxArea = 0; 
		for (int i = 0; i < height.length; i++) {
    
			for (int j = i + 1; j < height.length; j++) {
    
				int area = (j - i) * (height[i] > height[j] ? height[j] : height[i]); 
				maxArea = area > maxArea ? area : maxArea; 
			} 
		} 
		return maxArea; 
	} 

实现方式二：（双指针法减少时间复杂度，存在的其他问题：既有循环又有判断，用while更高效一些，减少了像i这种非必要的变量，并且无需再判断退出条件；并且循环次数不够准确，效率不高）

	public static int maxArea1(int[] height) {
    
		int maxArea = 0; 
		int p = 0; 
		int q = height.length - 1; 
		for (int i = 0; i < height.length; i++) {
    
			maxArea = Math.max((q - p) * Math.min(height[p], height[q]), maxArea); 
			if (q > p) {
    
				if (height[p] > height[q]) {
    
					q--; 
				} else {
    
					p++; 
				} 
			} 
		} 
		return maxArea; 
	} 

实现方式三： （替换成while结果，减少了不必要的循环次数；）

	public static int maxArea2(int[] height) {
    
		int maxArea = 0; 
		int p = 0; 
		int q = height.length - 1; 
		while (p < q) {
    
			if (height[p] > height[q]) {
    
				maxArea = Math.max((q - p) * height[q], maxArea); 
				q--; 
			} else {
    
				maxArea = Math.max((q - p) * height[p], maxArea); 
				p++; 
			} 
		} 
		return maxArea; 
	}