C++で解く「最大水量コンテナ」問題 ― 二重ポインタでO(N)実装

問題概要

容器の壁の高さが配列として与えられ、その中で最大量の水を溜められる容器を見つけるのがこの問題の目標です。壁の高さは配列の要素で表され、2つの壁の間の距離（インデックスの差）が容器の幅として扱われます。たとえば、高さ Arr[i] と Arr[j] の壁の間の幅は j−i です（0 ≤ i < j ≤ N、N は壁の総数＝配列の長さ）。

水位は低い方の壁の高さまでしか上がりません。Arr[i] < Arr[j] なら水位は Arr[i] となり、幅は j−i なので、溜められる水の面積は次の式で表せます。

面積 ＝ min(Arr[i], Arr[j]) × (j − i)

この面積の最大値を求めればよいことになります。

入力例1

Arr[] = { 5, 1, 2, 3, 5 }

出力例1

Maximum water area : 20

考え方

壁の高さが 5, 1, 2, 3, 5 の場合、代表的な壁の組み合わせごとの面積は以下のようになります。

Arr[0](5) と Arr[4](5)：幅 4 → 面積 5×4 = 20
Arr[1](1) と Arr[4](5)：幅 3 → 面積 1×3 = 3
Arr[2](2) と Arr[0](5)：幅 2 → 面積 2×2 = 4
Arr[3](3) と Arr[0](5)：幅 3 → 面積 3×3 = 9

最大の面積となるのは 20 で、壁 Arr[0] と Arr[4] を使った容器が最も多くの水を溜められます。

入力例2

Arr[] = { 1, 5, 4, 3, 2, 4 }

出力例2

Maximum water area : 16

考え方

Arr[0](1) と Arr[5](4)：幅 5 → 面積 1×5 = 5
Arr[1](5) と Arr[5](4)：幅 4 → 面積 4×4 = 16
Arr[2](4) と Arr[5](4)：幅 3 → 面積 4×3 = 12
Arr[3](3) と Arr[1](5)：幅 2 → 面積 3×2 = 6
Arr[4](2) と Arr[1](5)：幅 3 → 面積 2×3 = 6

最大の面積は 16 で、壁 Arr[1] と Arr[5] を使った容器が最大の水量になります。

アルゴリズム（二重ポインタ法）

すべての壁のペアを総当たりで調べる方法もありますが、O(N²) の計算量が必要になり非効率です。ここでは、左右の端から同時に走査する二重ポインタ（Two Pointer）を使うことで、O(N) で解けます。

• 整数配列 walls[] に各壁の高さが格納されています。

• 関数 mostwater(int A[], int len) は高さの配列と要素数を受け取り、最大水量となる容器の面積を返します。

• 左端を指すインデックス l = 0、右端を指すインデックス r = len−1 とし、両端から配列を走査します。

• area は現在の容器の面積、maxarea はこれまでに見つかった最大面積を保持します。初期値はどちらも 0 です。

• A[l] と A[r] のうち低い方の高さが水位になるため、それを minwall に保存します。

• 2つの壁の間の幅はインデックスの差 (r − l) です。

• 現在の面積を minwall × (r − l) として計算し、maxarea より大きければ更新します。

• その後、低い方の壁に対応するポインタを内側へ移動します。高い方の壁を動かしても面積は増えないためです。

• l < r の間これを繰り返し、最後に maxarea を結果として返します。

C++ 実装例

#include<iostream>
using namespace std;

int mostwater(int A[], int len){
    int l = 0;        // 左側の壁のインデックス
    int r = len - 1;  // 右側の壁のインデックス
    int area = 0, maxarea = 0;
    int minwall;

    while (l < r){
        // 水位は低い方の壁の高さ
        minwall = A[l] <= A[r] ? A[l] : A[r];
        // 面積 ＝ 低い方の壁 × 幅(r - l)
        area = minwall * (r - l);
        // 最大面積を更新
        if (area > maxarea)
            maxarea = area;
        // 低い方の壁のポインタを内側へ移動
        if (A[l] <= A[r])
            l += 1;
        else
            r -= 1;
    }
    return maxarea;
}

int main(){
    int walls[] = {1, 5, 4, 3, 2, 4};
    int num = sizeof(walls) / sizeof(walls[0]);
    cout << endl << "Container with Most water has area:" << mostwater(walls, num);
}

出力

Container with Most water has area:16

まとめ

この問題は、「水位は低い方の壁で決まる」という性質を利用することで、全ペアを調べる O(N²) の総当たり法ではなく、両端から走査する二重ポインタ法により時間計算量 O(N)・追加メモリ O(1) で効率的に解けます。LeetCode の「11. Container With Most Water」として知られる定番問題であり、配列操作や双方向探索の理解を深めるのに最適な題材です。