Pythonで解く「最大の水を溜められるコンテナ」問題 ― 二ポインタ法による効率的な実装

問題の概要

n個の非負整数 a₁, a₂, ..., a_n が与えられ、それぞれの値は座標 (i, a[i]) 上の点を表すものとします。i番目の縦線は、端点 (i, a[i]) と (i, 0) を結ぶ線分です。この中から2本の線を選び、x軸とともにコンテナ(容器)を形成したときに、最も多くの水を溜められる組み合わせを見つけるのがこの問題の目的です。

例えば、配列が [1,8,6,2,5,4,8,3,7] の場合を考えてみましょう。

図の網掛け部分では、高さが7、横幅が7区間あるため、合計面積は 7 × 7 = 49 となります。これが求める出力です。

解法のアプローチ(二ポインタ法)

この問題は「二ポインタ(ツーポインタ)法」を使うことで、全探索(O(n²))よりもはるかに効率的に解けます。考え方のポイントは、水量は「2本の線のうち低い方の高さ × 線同士の距離」で決まるという点です。そのため、低い方の線を内側へ動かしても面積が増えることはないため、低い側のポインタだけを移動させていきます。

具体的な手順は以下の通りです。

• low := 0、high := 配列の長さ − 1、ans := 0 として初期化する
• low < high の間、次を繰り返す:
  • height[low] < height[high] の場合:min_h := height[low]、min_ind := low とする
  • それ以外の場合:min_h := height[high]、min_ind := high とする
  • ans := max((high − low) × min_h, ans) で最大値を更新する
  • min_ind が low 側なら low を1増やし、そうでなければ high を1減らす
• 最後に ans を返す

このアルゴリズムの計算量は時間 O(n)、空間 O(1) であり、非常に効率的です。

実装例

以下はPythonでの実装例です。

class Solution(object):
    def maxArea(self, height):
        low = 0
        high = len(height) - 1
        ans = 0
        while low < high:
            if height[low] < height[high]:
                min_height = height[low]
                min_height_index = low
            else:
                min_height = height[high]
                min_height_index = high
            ans = max(((high - low)) * min_height, ans)
            if low + 1 == min_height_index + 1:
                low += 1
            else:
                high -= 1
        return ans

ob1 = Solution()
print(ob1.maxArea([1,8,6,2,5,4,8,3,7]))

入力

[1,8,6,2,5,4,8,3,7]

出力

49

まとめ

「最大の水を溜められるコンテナ」問題は、左右から中央へ向かってポインタを動かす二ポインタ法により、O(n) の計算量で解ける代表的な配列操作の問題です。低い方の壁が水量の上限になるという性質を理解すれば、なぜ片側だけポインタを動かせばよいのかが直感的に分かります。コーディング面接でも頻出のテーマなので、ぜひマスターしておきましょう。