目录

• 1.题目
• 2.思路
• 3.代码

1.题目

盛最多水的容器:

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

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2.思路

看到这道题我最开始想到的还是直接两个for循环遍历得出最大值

public class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        for(int i = 0;i < height.length - 1;i ++){
            for(int j = height.length - 1;j > i;j --){
                int tmp = Math.min(height[i], height[j])*(j - i);
                ans = Math.max(tmp,ans);
            }
        }
        return ans;
    }
}

不出所料的超时了
O(N²)

看了下官方的题解（自己还是做不出来orz）
运用了双指针的思路：
1.
将数组的第一个元素和最后一个元素设为最初的两个指针

双指针指向数组的左右边界，数组的所有元素都可以成为指针。
那么我们要如何移动这两个边界来计算出最大的面积呢？

2.
从上面的图我们会想到先移动左侧的指针向右侧一步，也就是两个指针指向的值更小的那一侧去移动，我们才可能得到更大的面积值。
证明以上思路的过程如下：

假设我们去移动更大的一侧的指针：

设左右边界的指针指向的数分别为 I1 和 J1，设 I1 < J1, 数组元素个数为 n，所包围的面积为 S

∴ S1 = min(J1, I1) * n = I1 * n; //最初所包围的面积 

假设此时将右侧指针向左移动，指向的数为 j2 

if(J2 >= J1) 
	S2 = min(J2, I1) * (n - 1) = (I1 or J2) * (n - 1) < S1
else 
	S2 = min(J2, I1) * (n - 1) = I1 * (n - 1) < S1
	
由此可知无论如何移动右侧指针 S 的值都不会比 S1大。

剩下的就是当两个指针重合时， 得出的最大面积就是我们的答案
代码如下

3.代码

public class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int max = 0;
        while (i != j) {
            int s = Math.min(height[j], height[i]) * (i - j);
            max = Math.max(max, s);
            if (height[j] <= height[i]) {
                j++;
            }
            else {
                i++;
            }
        }
        return max;
    }
}

小感悟：第一次这么认真的做了一道题，之前断断续续的做过几道题但都不太精，
这个文章也写的很差，图画的很难看，这篇文章和这道题就算是我leetcode的一个全新的开始吧，
今后每道题都会写这么一篇文章，尽量跟上卷王们的步伐（哭