Container With Most Water
非負整数のリスト height が与えられます。i 番目の線は、高さ height[i] で位置 i に立つ垂直な壁です。任意の2本の線と地面で容器が形成され、短い方の線の高さに2本の線の間の距離を掛けた量の水を入れられます。他の線は邪魔になりません。1組の線で入れられる水の最大量を返してください。
関数
- heightinteger-array
- 位置 0、1、2 などにある行の高さ
- 戻り値integer
- 2本の線が保持できる水の最大量
制約
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- 答えは最大でも 108 なので、32 ビット整数に収まります。
例
- 入力
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- 出力
- 36
- 説明
- 位置1と7、高さ7と6の線は、間隔が6あり、6 × 6 = 36を保持します。最も高い2本の線である位置1と5の高さ7の線は、7 × 4 = 28しか保持しません。
- 入力
- height = [4, 4]
- 出力
- 4
- 説明
- 2本の線でちょうど1つのコンテナができます。高さは4、幅は1なので、4を保持します。
発展問題
ここでは、2本の線の間にある線は無視されます。すべての線が太い棒だとしたら、その間にどれだけの水がたまるでしょうか？これも O(n) で計算できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まず、外側の2本の線から始めましょう。この2本が最も幅の広いコンテナを作ります。どちらかの端を内側に動かすと、幅が1単位減ります。それを補える可能性があるのは、2本のうちどちらでしょうか？
水は短い方の線でせき止められます。長い方の線を内側に動かすと、そのせき止める高さは変わらず幅だけが狭くなるため、決して有利にはなりません。短い方の線を置き換える場合にのみ、改善の可能性があります。
両端にポインターを置きます。その間の水の量を測り、最大の値を記録してから、短い方の線にあるポインターを内側へ1つ移動します。ポインターが出会ったら終了します。
解説
n²/2 個のペアをすべて確認すると、10^4 本の線に対して 5 × 10^7 回の積の計算が必要になります。水の量はペアのうち短い方の線だけに依存するため、ある線が作れる最も広い容器の短い側になった時点で、その線を使うそれより狭い容器で、より多くの水を入れることはできません。2 つのポインターを使えば、両端から 1 回走査するだけで済みます。
すべてのペアを確認する
正しいが、最大のテストでは終わらない
考え方
一組 i < j は min(height[i], height[j]) × (j - i) を表します。水は短い方の壁からあふれ、底面の幅は j - i です。すべての組み合わせを試し、最大値を保持します。
n 本の線からは n(n-1)/2 個の組み合わせができます。10^4 本の場合は約 5 × 10^7 個で、n が 2 倍になるたびにその数は 4 倍になります。
アルゴリズム
bestを0に設定します。- 各
iについて、その後の各jに対し、min(height[i], height[j]) × (j - i)を計算します。 bestとその値のうち、大きい方を保持します。bestを返します。
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return best最も高い行を先に
考え方
線 i が容器の短い側なら、相手は少なくとも同じ高さの任意の線です。したがって、そのような容器のうち最良のものは、少なくとも同じ高さの線の中で最も遠い線と組み合わせたものです。
線を高い順に並べます。線 i の番が来ると、すでに配置された線はすべて少なくとも同じ高さで、最も遠い線は配置済みのインデックスの左端または右端、lo または hi です。したがって、線 i が保持できる水の量は最大でも height[i] × max(i - lo, hi - i) であり、短い方の線の番が来たときに最良の容器が数えられます。同じ高さの線が2本ある場合、後から配置された線は、先に配置された線を相手として見ることになります。
最初の例では、位置1と5にある7の線が最初に来て、28を保持します。次に位置7の6の線は lo = 1 と認識し、36を保持します。ソートには O(n log n) の時間と O(n) のメモリが必要です。
アルゴリズム
- インデックスを高さの高い順に並べ替えます。
loとhiをその順序の最初のインデックスに設定し、bestを 0 に設定します。- 次の各インデックス
iについて、height[i]にi - loとhi - iの大きい方を掛け、その最良値を保持します。 loとhiを更新してiを含めます。bestを返します。
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return best両端からの2つのポインター
考え方
最も幅の広いコンテナから始めます。left = 0 と right = n-1 とし、height[left] ≤ height[right] だとします。直線 left を使うほかのすべてのコンテナでは、より近い直線と組み合わせるため、幅が狭く、高さも height[left] 以下になります。測定した水の量を上回るものはないので、直線 left の役目は終わり、left を右へ1つ移動します。高さが等しい場合は両方の直線の役目が終わるため、どちらを移動してもかまいません。
各ステップで直線を1本ずつ対象から外すため、n-1ステップ後にポインターは出会います。最良のペアが飛ばされることはありません。2本の直線のうち先に対象から外されるとき、その時点で測定されるコンテナには少なくとも同じ量の水が入っています。
最初の例では、位置0と7には21の水が入り、3の直線を対象から外します。位置1と7には36の水が入り、6の直線を対象から外します。残りの組み合わせに入る水の量は15、28、12、10、2です。
アルゴリズム
left = 0、right = n-1、best = 0を設定します。left < rightの間、min(height[left], height[right]) × (right - left)を計算し、最大値を保持します。height[left] < height[right]の場合、leftを右に1つ進めます。それ以外の場合は、rightを左に1つ進めます。- ポインターが一致したら、
bestを返します。
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
落とし穴と境界ケース
- より高い線を動かすこと。最初の例で答えが36ではなく21になるのは、位置7の6が位置1の7に出会う前に離れてしまうためです。
- より高い線、または2本の平均を高さとして使うこと。水は低い方の壁を越えてこぼれるため、高さは小さい方の値になります。
- 幅を
j - i + 1として測ること。位置iとjの線の間隔はj - iなので、[4, 4]が保持する量は8ではなく4です。 - 答えは最も高い線、または両端の線の組み合わせになると思い込むこと。最初の例では、2本の7が保持する量は28、両端の線の組み合わせでは21ですが、答えは36です。
よくある質問3
Container With Most Water の時間計算量は何ですか？
2ポインターによる解法は、各ステップで1つのポインターを内側へ1位置移動するため、時間計算量は O(n)、追加の空間計算量は O(1) です。すべてのペアを確認すると O(n²)、高さで線をソートすると O(n log n) かかります。
短い方の線でポインターを動かすのはなぜですか？
水の高さは短い方の線によって制限されます。その線を残すほかのどの容器も、組み合わせる相手がより内側にあるため、幅が狭く、高さも同じかそれ以下です。測定した容器を上回るものはないので、答えを損なうことなく短い方の線を捨てられます。
Container With Most Water は貪欲法の問題ですか？
はい。各ステップで、取り消されることのない局所的な選択をします。短い方の線を捨てます。この選択が安全なのは、候補から外されるコンテナはどれも、すでに測定したものより良くないためです。そのため、この問題は貪欲法と両端ポインターの両方に分類されます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxArea(height):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
height = [3, 7, 2, 5, 4, 7, 3, 6]
期待される出力
36