難易度：中程度#
問題：#
整数配列 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;
}
結果は効果的でした