1 题目描述
- 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
2 题目示例
输入：[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 题目提示
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
4 思路
矩阵的面积与两个因素有关：
矩阵的长度：两条垂直线的距离
矩阵的宽度：两条垂直线其中较短一条的长度
因此，要矩阵面积最大化，两条垂直线的距离越远越好，两条垂直线的最短长度也要越长越好。
我们设置两个指针 left 和 right，分别指向数组的最左端和最右端。此时，两条垂直线的距离是最远的，若要下一个矩阵面积比当前面积来得大，必须要把 height[left] 和 height[right] 中较短的垂直线往中间移动，看看是否可以找到更长的垂直线。
对于这种问题，不要想整体，而应该去想局部；本质就是动态规划思路，考虑如何处理没一个子问题即：位置 i，能装下多少水。
5 我的答案
/**
* 双指针解法
* 时间复杂度降 O(N)，空间复杂度 O(1)
*/
public int maxArea(int[] height) {
int size = height.length;
int result = 0;
int left_max = 0, right_max = 0;
int left = 0, right = size - 1;
while (left < right) {
left_max = Math.max(left_max, height[left]);
right_max = Math.max(right_max, height[right]);
int currentArea = 0;
//用 left 和 right 两个指针从两端向中心收缩，一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案
//矩形的高度是由 min(height[left], height[right]) 即较低的一边决定的：
//移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大.
if (left_max < right_max) {
currentArea = left_max * (right - left);
left++;
} else {
currentArea = right_max * (right - left);
right--;
}
result = Math.max(result, currentArea);
}
return result;
}
