Container With Most Water

すべての容器は、位置 i < j のペアです。水位は低い方の壁を越えてあふれるまで上がり、壁の間の底面の幅は j - i なので、このペアが保持できる水の量は min(height[i], height[j]) × (j - i) です。すべてのペアを試し、最大値を保持すれば、定義上それが答えになります。

問題はペアの数です。n 本の線からは n(n-1)/2 個のペアができます。線が 10^4 本の場合は約 5 × 10^7 個で、リストの長さが 2 倍になるたびにその数は 4 倍になります。コンパイル言語なら一瞬で処理できますが、Python、Ruby、R では何秒もかかり、n が 10^5 に達すると、どの言語でもペアの数が増えすぎてしまいます。

容器を、短い方の辺の側から見てみましょう。辺 i が短い方の辺なら、水の量は height[i] と距離の積になり、相手の辺は少なくとも同じ高さであればどれでも構いません。したがって、i が短い方の辺となる容器のうち最良のものは、少なくとも同じ高さの辺の中で最も遠い辺と組み合わせたものです。

そのような相手をすばやく見つけるには、辺を高い順から低い順に並べます。辺 i の番になると、それより前に並べられた辺はすべて少なくとも同じ高さであり、その中で最も遠い辺は、配置済みのインデックスの最左端または最右端にあります。この2つのインデックス lo と hi を記録しておけば、辺 i が保持できる水の量は最大で height[i] × max(i - lo, hi - i) です。最良の容器は短い方の辺が処理されるときに数えられるため、答えはこれらの値の最大値です。

最初の例では、位置1と5にある2つの7が最初に処理され、28の水を保持します。次に位置7の6が処理され、このとき lo = 1、hi = 5 で、6 × 6 = 36の水を保持します。これを上回る短い辺はありません。同じ高さの辺はどの順番で処理しても構いません。同じ高さの2つの辺のうち、後に処理される方は、先に処理された方を相手として見ることになります。

ソートには O(n log n)、走査には O(n) かかり、十分高速です。ただし順序を保持するために O(n) のメモリが必要で、次の方法ではソートもメモリも不要になります。

最も幅の広い容器から始めます。left = 0、right = n-1として、その容量を測ります。ここで2本の線のうち1本を取り除けますが、選択肢は決まっています。短いほうを取り除きます。height[left] ≤ height[right]だとします。線leftを使うほかのどの容器も、rightより近くにある線と組み合わせるため、幅が狭く、高さもheight[left]以下です。測定した水の量を上回るものはないので、線leftの役目は終わり、leftを1つ右へ進めます。背の高いほうの線を動かすと、高さの上限はそのままに幅だけが狭くなるため、結果は悪くなる一方です。2本の線の高さが等しい場合は、どちらの線も役目を終えているので、どちらを動かしてもかまいません。

各ステップで1本の線を永久に候補から外すため、n-1ステップ後にはポインターが合流します。最適なペアが見落とされることはありません。その2本の線のどちらかが初めて取り除かれるとき、その時点で測定した容器には、少なくとも同量の水が入ります。

[3, 7, 2, 5, 4, 7, 3, 6]では、位置0と7が3 × 7 = 21を保持します。3のほうが低いため、leftを1へ進めます。位置1と7は6 × 6 = 36を保持し、今度は6のほうが低いため、rightを6へ進めます。その後の容器が保持する水の量は15、28、12、10、2なので、答えは36のままです。