难度：中等#
题目：#
给定一个长度为 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;
}
結果果然有效