一、题目描述
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器
「示例 1:」
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
「示例 2:」
输入：height = [1,1]
输出：1
「示例 3:」
输入：height = [4,3,2,1,4]
输出：16
「示例 4:」
输入：height = [1,2,1]
输出：2
「提示：」
- n = height.length
- 2 <= n <= 3 * 104
- 0 <= height[i] <= 3 * 104
二、思路分析：
这道题其实就是求最大面积，而面积的求法就是 底*高；
这道题的 底求法比较简单，就是两个下标的差值；高是 某段数组中最小的值。难就难在怎么找到 最大的 底 * 高 的组合。这道题不断的需要移动数组下标来寻找最大的面积，所以运用 「双指针」 的思路来做就很合适，连个指针初始指向最左侧最右侧，至于怎么移动，移动那个则需要通过所在的值来判断，这里做法是那边的值小那个指针就向对方移动，原因是：
先用 s 表示面积；heigth[left]表示左侧指针的值；heigth[right] 表示右侧指针的值。
s = Math.min(heigth[left], heigth[right]) * (right - left);
「如果移动的值大的指针，那么所得到的面积 s 一定不大于当前面积。」
大家想想是不是这个理儿，因为 面积是由最小值决定的，如果移动最大值，那么无论它移动后的值多大，都一定不大于当前的面积。所以每次移动都要移动值小的指针。接下来上代码可能会更清晰一些。
三、AC代码
class Solution {
public int maxArea(int[] height) {
if (height == null || height.length < 1) {
return 0;
}
int ans = 0;
int left = 0, right = height.length - 1;
// 当两个指针没有重合时
while (left < right) {
// 求面试的方程式
int area = Math.min(height[left], height[right]) * (right - left);
// 取最大的面积
ans = Math.max(ans, area);
// 那个值小就移动那个指针
if (height[left] <= height[right]) {
left ++;
} else {
right --;
}
}
return ans;
}
}
四、总结
这道题主要是要想到用 双指针的方式来解决，因为双指针可以更动态的调整下标值；然后就是 指针的移动算法尤为重要，什么时候移动，怎么移动的问题。
