难度：Medium#
题目：#
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height [i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解析#
一眼 “秒” 了？#
粗看这道题，这不是很简单吗。用两个循环，循环计算水量并比较最大水量不就行了。甚至不需要记录在哪个时刻水最大。“秒” 了
public int maxArea(int[] height) {
//遍历
int max = height.length;
int maxarea = 0;
for (int n = 0; n < max; n++) {
for (int m = n; m < max; m++) {
int temp = (m - n) * Math.min(height[n],height[m]);
maxarea = Math.max(maxarea,temp);
}
}
return maxarea;
}
结果
好家伙，这么搞。数据太多了，两个循环导致处理超时了。
重新出发#
问题是两个循环嵌套导致的，所以目标就是减少循环，做到一次循环甚至更少。
看了提示需要用两个指针。从左右端点作为出发点。如果能做到一次只移动一个方向上的指针，那个就可以做到只循环一次。水量由水池的底（就是两个指针的距离）和高（两个指针所对应的高的最小值）的乘积决定。水池的底，在向中移动过程中只会不断变小。而高是两个指针对应高的最小值，如果说移动高的指针因为取的是最小值所以水池的高没有变化。水量甚至还会变小。移动水池低的边才有可以增加水量。
于是乎，就决定方式为循环一次，每次移动小的边，比较每次的水量和记录的最大水量，找出真正的最大水量。
public int maxArea(int[] height) {
//双指针
int max = height.length;
int i = 0;
int j = max - 1;
int maxarea = 0;
for (int n = 0; n < max; n++) {
maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return maxarea;
}
结果成了
继续优化#
我发现，在左右指针向中间移动的过程中。如果移动后的指针高度比移动前更低，那是不是就不用判断水池 “水量”，因为肯定变少了，直接继续移动。于是我用了两个标识来记录，提高代码的执行速度。
于是嘎嘎干
public int maxArea(int[] height) {
//双指针优化
int max = height.length;
int i = 0;
int j = max - 1;
int maxarea = 0;
//两边的标识
int maxHeightI = height[i];
int maxHeightJ = height[j];
//记录上次是左边指针（0）移动还是右边指针（1）移动
int flag = 0;
for (int n = 0; n < max; n++) {
if (flag == 0) {
if (height[i] < maxHeightI) {
i++;
continue;
}else {
maxHeightI = height[i];
}
}
if (flag == 1) {
if (height[j] < maxHeightJ) {
j--;
continue;
}else {
maxHeightJ = height[j];
}
}
maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
if (height[i] < height[j]) {
i++;
flag = 0;
} else {
j--;
flag = 1;
}
}
return maxarea;
}
结果果真有效