問題
等しいheights を
- 間に
ある 板は 水を さえぎりません。 選んだ 2 本だけで 量が 決まります heightsの長さは 2 以上 100000 以下、 高さは どれも 0 以上 10000 以下です
入力と出力の例
例 1
両端の
入力
heights = [3, 1, 4, 2, 5]出力
12例 2
いちばん高い
入力
heights = [2, 9, 1, 1, 8, 3]出力
24例 3
板が 2 本だけでも、
入力
heights = [6, 6]出力
6面接での聞かれ方
面接では、
- 「棒の
高さの 配列が あります。 2 本選んで、 いちばん 多く 水を ためられる 量を 返してください」 - 2 重の
繰り返しを 見せると、 「O(n) に できますか？」と続きます - ツーポインタで
書くと、 必ず 「なぜ低い方を 動かして よいのですか？ 答えを 飛ばしませんか？」と 聞かれます
書ける
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
両端の 2 本から
段 3
どちらの
段 4
この
解答
Python
Python
def max_water(heights):
left = 0
right = len(heights) - 1
best = 0
while left < right:
a = heights[left]
b = heights[right]
width = right - left
area = min(a, b) * width
best = max(best, area)
if a < b:
left += 1
else:
right -= 1
return bestJavaScript
JavaScript
function maxWater(heights) {
let left = 0;
let right =
heights.length - 1;
let best = 0;
while (left < right) {
const a = heights[left];
const b = heights[right];
const width = right - left;
const area =
Math.min(a, b) * width;
best = Math.max(best, area);
if (a < b) {
left++;
} else {
right--;
}
}
return best;
}Go
Go
func maxWater(
heights []int,
) int {
left := 0
right := len(heights) - 1
best := 0
for left < right {
a := heights[left]
b := heights[right]
width := right - left
area := min(a, b) * width
if area > best {
best = area
}
if a < b {
left++
} else {
right--
}
}
return best
}Go の min は 1.21 からif で
計算量
- 時間は O(n) です。
1 回まわる ごとに どちらかの 指が 1 つ内側へ 進み、 2 つの 指が 出会えば 終わります - 使う
記憶は O(1) です。 指 2 つと、 量を 入れる 置き場だけです - 段 1 の
全部の 組を 試す 書き方は、 時間が O(n²) です。 段 4 の 「外してよい理由」が あるから、 組の 大半を 試さずに済みます
よく
- 高い方の
指を動かす。 例 2 の [2, 9, 1, 1, 8, 3]で、両端の 2 と 3 から 高い方の 3 を 動かすと、 9 と 8 の 組 (量 24) に たどり着く 前に 左の 2 が 残り続け、 答えを 取り逃します - 高さを
足したり、 高い方を 掛けたりする。 水は 低い方の 板の 高さまでしか たまりません。 量は 低い方の 高さと 位置の 差の積です - 位置の
差を right - left + 1にする。 板と板の 間の 距離なので、 隣どうしなら 1 です。 例 3 の [6, 6]が 12 になっていたら、 ここを疑います - 間に
ある 板も 壁に なると考える。 この 問題では 間の 板は 水を さえぎりません。 雨水が どれだけたまるかを 足し合わせる 問題とは別物です
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「全部の
組を 試すと O(n²) です。 両端から 始めて、 低い方の 指だけを 内側へ 寄せます。 高い方を 動かしても、 高さは 低い方で 頭打ちのまま 幅だけ減るので、 量は 増えません。 逆に、 低い方の 板は いまの 相手より 内側の 誰と 組んでも、 いまより 多くは ためられないので、 候補から 外して よいです。 時間は O(n)、 記憶は O(1) です。」
書き終えたら、
「例 2 の
[2, 9, 1, 1, 8, 3]でたどります。 2 と 3 で 量は 10 です。 低い 2 の 方を 動かして、 9 と 3 で 12 です。 今度は 3 が 低いので 右を 動かして、 9 と 8 で 24 に なります。 8 が 低いので 右を 動かすと、 9 と 1 で 2、 さらに 9 と 1 で 1 に なり、 指が 出会って 終わります。 いちばん 大きいのは 24 です。」