Largest Rectangle in Histogram
ヒストグラムは、隙間なく横に並んだ幅 1 単位の棒の列です。heights[i]は棒iの高さです。ヒストグラム内の長方形は、隣り合う棒の連続した範囲を覆い、その高さはその範囲で最も低い棒の高さを超えることはできません。
このような長方形が取りうる最大の面積を返してください。
関数
- heightsinteger-array
- 左から右に向かって、各バーの高さ
- 戻り値integer
- ヒストグラムに収まる最大の長方形の面積
制約
1 ≤ heights.length ≤ 2 × 1040 ≤ heights[i] ≤ 105- 各バーの幅は1単位なので、バー
iからjまでの長方形の幅はj-i+1単位です。
例
- 入力
- heights = [2, 5, 6, 3, 4, 1]
- 出力
- 12
- 説明
- 4本の棒5、6、3、4はすべて高さが少なくとも3あるため、高さ3の長方形がこれらすべてにまたがります。3 × 4 = 12。最も高い2本の棒である5と6では、5 × 2 = 10にしかなりません。
- 入力
- heights = [1, 8, 1, 1]
- 出力
- 8
- 説明
- 8の棒だけなら、8 × 1 = 8 になります。幅がそれより広い長方形には1の棒が含まれるため、最大でも1 × 4 = 4です。
- 入力
- heights = [3, 3, 3, 3]
- 出力
- 12
- 説明
- 4 本の棒はすべて高さが 3 なので、ヒストグラム全体は 1 つの長方形になります：3 × 4 = 12。
提出時に隠しテスト+17件
発展問題
各棒の幅がそれぞれ異なり、その幅が2つ目の配列で与えられるとします。1回の走査で解くスタック解法では、何が変わるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最大の長方形は、その下にある少なくとも1本の棒の上端に接しています。もし接していなければ、長方形をもっと高くできます。そこで、それぞれの棒を高さを決める棒として試してみましょう。その高さとちょうど同じ高さの長方形は、どれだけの幅にできるでしょうか？
棒
iと同じ高さの長方形は、左右それぞれで厳密に低い棒にぶつかるまで広がります。すべての棒について、左右それぞれで最も近い低い棒が分かれば、各棒から面積の候補が1つずつ得られ、候補はn個だけです。下から上へ高さが増加するインデックスのスタックを保持します。スタックの一番上の高さ以上ではない棒が現れたら、一番上の棒はそれより右へ進めないため、取り出します。その長方形は、新しいスタックの一番上と現在の棒の間にある棒を覆います。末尾に高さ0の棒を置くと、残っているものがすべて取り出されます。
解説
長方形はどの棒から始めてもどの棒で終わってもよく、高さは覆う範囲内の最も低い棒によって決まるため、棒のすべての連続区間を試すと、およそ n²/2 ステップかかります。この問題を解くには、問いを逆転させます。最適な長方形の高さは、ちょうどその中にある棒のいずれかの高さです。したがって、各棒は、より低い棒に遮られるまでどこまで広がれるかだけを把握すればよいのです。単調スタックを使えば、まず2回の走査で、次に1回の走査で、すべての棒についてその境界を見つけられます。
実行のたびに最小値を更新してみましょう
正しいが、最大のテストでは終わらない
考え方
長方形は、隣り合う棒の区間をstartからendまで覆い、その高さは区間内で最も低い棒によって制限されます。そこで、すべての区間を試します。startを固定し、endを棒1本分ずつ伸ばしながら、それまでに見つかった最小の高さを保持します。その区間における最良の長方形の面積はlowest × (end-start+1)です。
[2, 5, 6, 3, 4, 1]では、5から始めます。区間ごとの面積は、5 × 1 = 5、次に6を加えると5 × 2 = 10、3が加わると3 × 3 = 9、4を加えると3 × 4 = 12、1を加えると1 × 5 = 5です。答えは12です。区間を伸ばすたびにlowestを更新すれば、各ステップをO(1)で処理できるため、最小値を求めるために区間を再走査する必要はありません。
この方法が正しいのは、すべての長方形が何らかの区間を覆い、固定した区間に収まる最も高い長方形の高さは、ちょうど最も低い棒の高さになるからです。遅いのは、区間の数がn(n+1)/2だからです。棒が2 × 10^4本の場合、約2 × 10^8個になります。この個数は棒の高さにはまったく左右されません。ほとんどの区間は、終端に達するずっと前に低い棒によって制限されますが、力まかせの方法ではそれでも区間を伸ばし続けます。
アルゴリズム
bestを0に設定します。- 各
startについて、lowestをheights[start]に設定します。 startから最後の棒までの各endについて、その棒がより短ければ、lowestをheights[end]に下げます。lowest × (end-start+1)でbestを更新します。bestを返します。
def largestRectangleArea(heights):
n = len(heights)
best = 0
for start in range(n):
lowest = heights[start]
for end in range(start, n):
# The rectangle over start..end is as tall as the lowest bar in it.
lowest = min(lowest, heights[end])
best = max(best, lowest * (end - start + 1))
return best左右それぞれで最も近い、より短い棒
考え方
探索の視点を変えましょう。最大の長方形には、その高さとちょうど同じ高さの棒が少なくとも1本含まれています。そうでなければ、長方形をもっと高くできるからです。したがって答えは、すべての棒 i について、高さがちょうど heights[i] で、可能な限り幅を広げた長方形のうち最大のものです。左右で、これより厳密に低い棒に出会うまで広がります。その棒のインデックスを left[i] と right[i] と呼び、存在しない場合は -1 と n を使います。長方形が覆うのはその間にある棒だけなので、幅は right[i]-left[i]-1 です。候補は n²/2 個ではなく n 個になります。
すべての棒について left[i] を求めるには、インデックスを積むスタックを使い、左から右へ走査します。スタック内の高さは、底から頂上に向かって厳密に大きくなります。棒 i が来たら、棒の高さが heights[i] 以上であるインデックスをすべて取り除きます。それらの棒は、i やその後のどの棒に対しても、最も近い低い棒にはなり得ません。i の方が近く、かつ高さも同じか高いためです。最後に残ったスタックの頂上が、左側で最も近い低い棒です。その後、i をスタックに積みます。右から左へ同じ処理を行えば、right[i] が求まります。
[2, 5, 6, 3, 4, 1] の場合、走査の結果は left = [-1, 0, 1, 0, 3, -1] と right = [5, 3, 3, 5, 5, 6] になります。インデックス3にある高さ3の棒は、インデックス0の高さ2の棒とインデックス5の高さ1の棒に挟まれているため、その長方形の面積は 3 × (5-0-1) = 12 です。高さ6の棒は隣の棒に挟まれているため、面積は 6 × 1 にしかなりません。
各インデックスは各走査で1回プッシュされ、ポップされるのも最大1回なので、1本の棒が多くの要素をポップすることがあっても、2回の走査はいずれも O(n) です。その代わり、追加の配列が2つ必要になります。
アルゴリズム
- 空のスタックを使って、左から右へ進みます。各
iについて、スタックの先頭にある棒の高さがheights[i]以上である間、それを取り出します。スタックが空ならleft[i]に-1を設定し、そうでなければスタックの先頭の値を設定してから、iをスタックに追加します。 - 同じ方法で右から左へ進み、空のスタックには
nを使ってright[i]を埋めます。 - すべての
iについて、heights[i] × (right[i]-left[i]-1)を計算します。 - それらの面積のうち最大のものを返します。
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n # index of the nearest shorter bar on the left, or -1
right = [n] * n # index of the nearest shorter bar on the right, or n
stack = [] # indices whose heights rise strictly from bottom to top
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i in range(n):
# Bar i is the lowest bar of everything strictly between left[i] and right[i].
best = max(best, heights[i] * (right[i] - left[i] - 1))
return best単調スタックによる1回の走査
考え方
左から右への走査では、右側の境界をすでに見つけていますが、それを捨てています。棒 i が棒 t をポップするとき、heights[i] は heights[t] 以下なので、i が t の長方形の右端になります。また、スタック上で t の下にあるインデックスが左端になります。そこで、ポップした時点で長方形の面積を計算します。heights[t] × (i - below - 1) です。ここで below はスタックの新しいトップで、スタックが空になった場合は -1 です。
不変条件は次のとおりです。スタック上の高さは、下から上へ厳密に増加し、各要素の下にあるインデックスは、その要素より低い最も近い左側の棒を示します。 2本の棒の間にある棒はすべて、その要素自身か、後にその要素がポップした棒によって、それまでにポップされています。したがって、そのどれも要素より低くありません。ポップされない棒は端まで続くので、最後の棒を処理した後に、高さ0の棒をもう1本処理します。これはすべての棒より低いため、スタックを空にします。
[2, 5, 6, 3, 4, 1] を順に見ていきましょう。2、5、6をプッシュすると、スタックにはインデックス [0, 1, 2] が入ります。インデックス3の3は、6をポップし（面積 6 × (3-1-1) = 6）、続いて5をポップし（面積 5 × (3-0-1) = 10）、その後2のところで止まり、プッシュされます。次に4をプッシュします。インデックス5の1は、4をポップし（面積4）、続いて3をポップします。この長方形はインデックス1から4まで伸びます。3 × (5-0-1) = 12 です。さらに2もポップします（2 × 5 = 10。スタックが空なので幅は5です）。最後に追加した0は1をポップします（1 × 6 = 6）。最大面積は12です。
>= の条件でポップすると、同じ高さの棒によって、別の棒が早めに止められることがあります。これは問題ありません。同じ高さの棒がスタック上でその位置を引き継ぎ、同じ左境界を持ちます。そして後でポップされるとき、その長方形は連続する棒全体を覆います。[3, 3, 3, 3] では、最初の3本の3が幅1、2、3を記録し、最後の1本は最後に追加した0によって幅4でポップされ、面積は12になります。
アルゴリズム
- 空のインデックスのスタックから始め、
best = 0とします。 iを0からnまで動かし、現在の高さをheights[i]とします。ただし、i = nの場合は0とします。- スタックの一番上にある棒の高さが現在の高さ以上である間、それを
tとして取り出します。幅はi - below - 1です。ここでbelowは新しいスタックの一番上の値、または-1です。heights[t] × widthでbestを更新します。 iをプッシュします。bestを返します。
def largestRectangleArea(heights):
n = len(heights)
stack = [] # indices whose heights rise strictly from bottom to top
best = 0
for i in range(n + 1):
current = heights[i] if i < n else 0 # a bar of 0 past the end empties the stack
while stack and heights[stack[-1]] >= current:
# Bar i stops the popped bar on the right; the bar below it stops it on the left.
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best
落とし穴と境界ケース
スタックループは短く、ほとんどのバグは幅の計算か、最後に残った棒に関するものです。
- スタックに残っている棒を処理し忘れる。
[1, 2, 3, 4, 5]のように棒の高さが増加するヒストグラムでは、ループ中にポップされる棒がなく、最後に高さ0の番兵を追加しないと、答えとして9ではなく0を返してしまいます。 - ポップした棒自身のインデックスを基準に幅を測る。その長方形は、スタック上でその棒の下にある棒のすぐ右から始まり、棒自身の位置からではありません。
[2, 5, 6, 3, 4, 1]では、インデックス3にある高さ3の棒は、インデックス1から4まで広がります。i - tを使うと、幅は4ではなく2になります。 - ポップ後にスタックが空になったとき、誤った幅を使う。ポップした棒はそれまでで最も低い棒なので、その長方形はインデックス0まで遡り、幅は
iです。[2, 1, 2]では、高さ1の棒が3本すべてに広がり、面積は3になります。 - 2回走査する方法で、両側に同じ高さの棒があるときに処理を止める。すると、
[3, 3, 3, 3]では各棒の幅が1となり、答えとして12ではなく3を返してしまいます。境界を厳密に低い棒にするため、>=の条件でポップしてください。 - 最も高い棒、または最も幅の広い範囲が最大になると思い込む。
[2, 5, 6, 3, 4, 1]では、高さ6の棒でも、幅6本すべてでも答えにはなりません。中央の高さと中央の幅の組み合わせが答えになります。 - オーバーフロー。この場合、面積は
10^5 × 2 × 10^4 = 2 × 10^9に達しますが、それでも符号付き32ビット整数に収まります。上限がさらに大きい場合は、64ビット整数で乗算してください。
よくある質問4
ヒストグラム内の最大長方形の時間計算量は何ですか？
単調スタックを使う解法の実行時間は O(n)、追加の空間計算量は O(n) です。各インデックスは一度プッシュされ、一度ポップされ、各ポップでは定数時間の処理を行います。棒の連続区間をすべて試すと、実行時間は O(n²) となり、棒が 2 × 10^4 本の場合、約 2 × 10^8 ステップになります。
バーがポップされたときに、その長方形のサイズを測定するのはなぜですか？
ある棒は、その右側にある、自分より高くない最初の棒によってポップされるため、そこが長方形の右端になります。スタック上でその下にあるインデックスは、左側にある最も近い低い棒を示すため、そこが左端になります。ポップされた時点で両端がわかっており、面積は height × (i - below - 1) です。
ヒストグラム内の最大長方形は、分割統治法で解けますか？
はい。範囲全体で最も低い棒が最適な長方形の下に位置する場合、その面積は lowest × width になります。そうでなければ、その棒が範囲を左部分と右部分に分割し、それぞれを個別に解きます。線形走査で最小値を探す場合、ランダムな入力では O(n log n) ですが、ソート済みの入力では O(n²) になります。範囲最小値を求めるセグメント木を使えば、常に O(n log n) です。スタックのほうがシンプルで高速です。
ヒストグラム中の最大長方形は、0/1グリッド内の最大長方形にどのように使われますか？
グリッドを行ごとにたどり、各列について現在の行で終わる連続した1の個数を保持します。0が現れたら、その個数をリセットします。各行の個数がヒストグラムを形成し、その行で終わる1の最大長方形は、そのヒストグラム内の最大長方形です。行ごとにスタックを1回実行すれば、O(rows × cols)時間でグリッドを解けます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def largestRectangleArea(heights):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
heights = [2, 5, 6, 3, 4, 1]
期待値
12