難易度：中程度#
問題：#
整数配列 height の長さ n が与えられます。n 本の垂直線があり、i 番目の線の 2 つの端点は (i, 0) と (i, height [i]) です。
x 軸と共に容器を構成する 2 本の線を見つけ、その容器に最大限の水を入れることができます。
容器に入れることができる最大の水量を返します。
注意：容器を傾けることはできません。
解析#
一目でわかりましたか？#
この問題をざっと見ると、とても簡単ではありませんか。2 つのループを使用して、水の量を計算し、最大の水の量を比較するだけです。どの時点で水が最大であるかを記録する必要さえありません。すぐにわかりました。
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;
}
結果
おっと、これはまずいですね。データが多すぎて、2 つのループがタイムアウトしてしまいます。
もう一度やり直しましょう#
問題は 2 つの入れ子のループによって引き起こされるものなので、目標はループを減らし、1 回のループ、またはそれ以下にすることです。
ヒントを見ると、2 つのポインタを使用する必要があることがわかりました。左右の端点を出発点とします。片方の方向のポインタを 1 回の移動で済ませることができれば、1 回のループで済ませることができます。水の量は、水池の底（つまり、2 つのポインタの距離）と高さ（2 つのポインタに対応する高さの最小値）の積で決まります。水池の底は、中央に向かって移動する過程で常に小さくなります。高さは 2 つのポインタに対応する高さの最小値ですが、高いポインタを移動する場合は、最小値を取るため、水池の高さは変化しません。水の量はさらに減少する可能性さえあります。水池の低い側を移動することでのみ水の量を増やすことができます。
したがって、実際の最大の水の量を見つけるために、1 回のループで小さい側を移動し、各回の水の量を比較し、記録します。
public int maxArea(int[] height) {
//2つのポインタ
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;
}
結果はこちらです
さらに最適化#
左右のポインタが中央に向かって移動する過程で、移動後のポインタの高さが移動前よりも低い場合、水池の「水量」を判断する必要はないのではないかと気づきました。なぜなら、確実に減少するからです。そのため、コードの実行速度を向上させるために、2 つのフラグを使用して記録することにしました。
さあ、やってみましょう
public int maxArea(int[] height) {
//2つのポインタを最適化
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;
}
結果は効果がありました