単調スタックパターン
単調スタックを適用し、daily-temperatures、largest-rectangle-in-histogram、next-greater-elementをO(n)で解きます。
「単調スタックパターン」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
単調スタックとは
単調スタックとは、要素全体でソート順の不変条件を維持するスタックです。単調増加スタックでは、要素が下から上に向かって増加します。単調減少スタックでは、要素が下から上に向かって減少します。新しい要素によって不変条件が崩れた場合は、不変条件が復元されるまで要素をポップし、その後で新しい要素をプッシュします。
この単純な仕組みにより、単純に実装するとO(n²)の二重ループが必要になる「最も近い大きい要素」や「最も近い小さい要素」の問い合わせに、O(n)で答えられます。
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)次に大きい要素（LeetCode 496）
各要素について、右側にある最初の、厳密に大きい要素を見つけます。力任せの方法では、各位置から右方向を調べるためO(n²)かかります。単調スタックを使う方法では、インデックスを格納した単調減少スタックを維持します。より大きい要素が見つかったら、小さい要素のインデックスをすべてポップします。それらの「次に大きい要素」は現在の要素だからです。スタックに残ったインデックスには次に大きい要素がないため、答えは-1です。
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]循環配列における次に大きい要素
LeetCode 503「Next Greater Element II」は同じ問題ですが、配列を循環するものとして扱います。末尾に到達したら先頭に戻り、先頭から調べます。ポイントは、配列を2回（インデックス0から2n-1まで）走査し、元の配列へのインデックス指定にi % nを使うことです。重複処理を避けるため、プッシュするインデックスは[0, n-1]の範囲にあるものだけにします。
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Daily Temperatures：完全解説
LeetCode 739をもう一度取り上げます。各日について、より気温が高くなるまで何日かかるかを求めます。単調スタックには、気温が降順になる日のインデックスを格納します。より気温の高い日iが見つかったら、スタックから気温の低い日のインデックスjをすべてポップし、result[j] = i - jを記録します。スタックに残った日は、より気温の高い日が見つからなかったため、結果は0のままです。
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]前のより小さい要素
「前のより小さい要素」の問い合わせでは、各要素について、左側にある最も近い小さい値を求めます。左から右へ処理し、単調増加スタックを使用します。インデックスiをプッシュする前は、スタックのトップが前のより小さい要素です。これは、nums[i]より大きいすべての要素が、以前の挿入時にすでにポップされているためです。以前の挿入では、より大きい要素がそれらをポップする処理が行われています。
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]ヒストグラム内の最大長方形
LeetCode 84「Largest Rectangle in Histogram」では、インデックスの単調増加スタックを使用します。各棒について、現在の棒より高い棒をすべてポップします。ポップされた棒hごとに、右境界は現在のインデックスi、左境界は新しいスタックのトップ+ 1です（スタックが空の場合は0です）。面積はh × (right - left)で求めます。高さ0の番兵を追加して、最後に残ったすべての棒もポップさせます。
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1最大長方形（LeetCode 85）
LeetCode 85「Maximal Rectangle」は、ヒストグラムの問題を2次元の二値行列に拡張したものです。各行について棒の累積高さを計算します。matrix[row][col] == '1'の場合、高さはこのセルを含め、上方向に連続する1の数になります。その後、各行の高さ配列に「ヒストグラム内の最大長方形」アルゴリズムを適用します。m×n行列に対する計算量はO(m × n)です。
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Trapping Rain Water：スタックによる方法
LeetCode 42「Trapping Rain Water」をスタックで解くには、インデックスの単調減少スタックを維持します。より高い棒が見つかると、谷が形成されます。谷の底をポップし、水の幅を(current_index - stack_top - 1)、高さを(min(current_bar, new_stack_top_bar) - valley_height)として計算します。すべての寄与を合計します。計算量はO(n)、空間計算量はO(n)です。
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9単調スタック問題の見分け方
単調スタックが適した問題には、次または前の、より大きい／より小さい要素を求めるもの、各要素の答えが特定の方向にある要素に依存するもの、各要素について左または右を走査する単純なO(n²)解法があるものなどがあります。スタックには、後続の要素の答えになる可能性がある候補を格納し、より良い候補が現れたらすぐに破棄します。
まず、増加スタック（次または前のより小さい要素を求める場合）と減少スタック（次または前のより大きい要素を求める場合）のどちらを使うか、そしてどの方向から処理するかを決めてください。
償却O(n)解析
単調スタックのアルゴリズムは、forループ内にwhileループがあるため、最初はO(n log n)やO(n²)に見えます。しかし、各要素は高々1回プッシュされ、高々1回ポップされます。プッシュ操作の総数はnで、ポップ操作の総数も最大でnです。そのため、すべての反復を通じた総作業量は2n回の操作、つまりO(n)の償却計算量であり、O(n²)ではありません。
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nまとめ：単調スタックの不変条件の選択
問い合わせの種類に応じてスタックの向きを選択してください。次に大きい要素には減少スタックを使い、現在の要素が大きいときにポップします。次に小さい要素には増加スタックを使い、現在の要素が小さいときにポップします。最大長方形には増加スタックを使い、より短い棒が現れたときにポップします。スライディングウィンドウの最大値には減少dequeを使い、両端から削除します。
コーディングの前に不変条件をコメントに書いておくと、ロジックが明確になり、デバッグも速くなります。
理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、単調スタックは新しい要素をプッシュする前に不変条件に違反する要素をポップすることで、ソート順の不変条件を維持します。また、単調減少スタックは次に大きい要素の問い合わせに、単調増加スタックは次に小さい要素の問い合わせに答えます。さらに、各要素は高々1回プッシュ・ポップされるため、総計算量はO(n)の償却計算量です。次は、スタックを使ったキューと、キューを使ったスタックを実装します。
よくある質問
「単調スタックパターン」レッスンは無料ですか？
はい。「単調スタックパターン」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「単調スタックパターン」で何を学びますか？
単調スタックを適用し、daily-temperatures、largest-rectangle-in-histogram、next-greater-elementをO(n)で解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「単調スタックパターン」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。