単調スタック：増加と減少
増加スタックまたは減少スタックを維持し、next-greater-elementとprevious-smaller-elementのクエリにO(n)で効率的に答えます。
「単調スタック：増加と減少」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
単調スタックとは
単調スタックとは、要素が常に整列された順序（下から上に常に増加、または常に減少）になるよう維持するスタックです。新しい要素をプッシュする前に、単調性の不変条件に違反する要素をすべてポップします。この制約付きのデータ構造により、本来ならO(n²)の二重ループが必要な問題をO(n)で解けます。
重要なポイントは、各要素がプッシュされるのもポップされるのも高々1回であることです。そのため、配列全体の走査で行われる操作の総数はO(n)であり、O(n²)ではありません。要素をポップした瞬間に、その要素が待っていた答えが見つかります。
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Next Greater Element I
Next Greater Element問題では、各要素について、右側で最初に現れる、それより大きい要素を求めます。力まかせのO(n²)の二重ループでは遅すぎます。単調減少スタックを使えば、これをO(n)で解けます。
要素を左から右へ処理します。要素iをプッシュする前に、スタックからnums[i]より小さい要素をすべてポップします。nums[i]が、それらすべてにとっての次に大きい要素だからです。すべての要素を処理した後もスタックに残っている要素には、右側にそれより大きい要素がありません（答えは-1です）。
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]次に大きい要素：アルゴリズムを追跡する
[2, 1, 2, 4, 3]を1ステップずつ追ってみます。次に大きい要素がまだ見つかっていないインデックスを保持する、単調減少スタックを使います。
- i=0、val=2：スタックは空なので、0 を push します。スタック: [0]
- i=1、val=1：1 < nums[0]=2 なので、1 を push します。スタック: [0,1]
- i=2、val=2：1 を pop します（nums[1]=1 < 2）。result[1]=2 となります。ここで nums[0]=2 は 2 未満ではないので、2 を push します。スタック: [0,2]
- i=3、val=4：2 を pop します（result[2]=4）。0 も pop します（result[0]=4）。その後、3 を push します。スタック: [3]
- i=4、val=3：3 < nums[3]=4 なので、4 を push します。スタック: [3,4]
- 終了時：スタック [3,4] の result は -1 です
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])前のより小さい要素
単調スタックは、前のより小さい要素（PSE）のクエリにも利用できます。これは各要素について、左側にある最も近い、より小さい要素を求めるものです。より大きい要素で pop する代わりに、より大きいか等しい要素で pop し、push する前にスタックのトップを PSE として記録します。
処理の方向が変わります。左から右へ処理する点は同じですが、pop するときに答えるのではなく、push する直前に答えます。その時点でのスタックのトップが、左側にある最も近い小さい要素です。スタックが空の場合、左側に小さい要素はありません（答え = -1 またはセンチネル値です）。
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Daily Temperatures：より暖かい日を待つ
Daily Temperatures問題（LeetCode 739）では、日ごとの気温が与えられ、各要素について、より高い気温になるまでの日数を配列として返します。これはまさに次に大きい要素のパターンですが、大きい値の代わりに日数（インデックスの差）を求めます。
インデックスを格納する単調減少スタックを使います。インデックス i でより高い気温が見つかったら、temps[j] < temps[i] を満たすスタック内のすべてのインデックス j を pop し、result[j] = i - j を設定します。スタックに残ったインデックスには、将来より高い気温の日がありません（result = 0 です）。
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]増加スタックと減少スタック：使い分け
適切なスタックの方向を選ぶことが重要です。
- 単調減少スタック（current > top のときに pop）：次に大きい要素と前のより大きい要素のクエリに答えます。daily-temperatures、largest-rectangle、trap-rain-water で使われます。
- 単調増加スタック（current < top のときに pop）：次に小さい要素と前のより小さい要素のクエリに答えます。株価のスパンや、キュー内で見える人の数を求める処理で使われます。
覚えておいてください。pop の原因となった要素が、pop された要素のクエリに対する答えになります。維持する不変条件に応じて、それは次に大きい要素または次に小さい要素です。
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)循環配列での次に大きい要素
Next Greater Element II（LeetCode 503）では、循環配列（末尾から先頭へ折り返す配列）が与えられ、次に大きい要素を求めます。ポイントは、インデックスを2倍にして配列を2回処理することです。0 から 2n-1 まで反復し、index % n で折り返し先のインデックスを求めます。二重に数えないように、0 から n-1 までのインデックス（1回目の走査）のみ push します。
別の方法として、2回目の走査では新しいインデックスを push せず、pop だけを行うこともできます。これにより、配列を実際に複製することなく循環配列の先読みを正しく処理でき、空間計算量を O(n) に保てます。
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]株価スパン問題
Stock Span問題では、日ごとの株価が与えられ、各日のスパンを計算します。スパンとは、その日の価格以下である連続した過去の日数です。これは前のより大きい要素の問題を別の形で表したものです。スパンは、当日から、厳密に高い価格だった最も近い日までの距離になります。
単調減少スタックを使います。日 i を処理するとき、現在の価格以下の価格を持つ日をすべて pop します。スタックが空でなければスパンは i - stack[-1]、空なら i + 1 です（これまでで最大の価格であることを表します）。その後、i を push します。
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6キュー内で見える人を求める単調スタック
Number of Visible People in a Queue問題では、身長の異なる人々がキューに並んでいます。人 i は、間にいるすべての人が両者より低い場合に、人 j（j > i）を見ることができます。この処理には単調減少スタックを使います。
右から左へ処理します。身長を格納する単調減少スタックを維持します。各人について、見える人数を数えます。低い人をすべて pop します（その人たちは見えますが、その先は遮られます）。その後もスタックが空でなければ、1 を加えます（最初に現れる、より高い人も見えるためです）。各人は push と pop をそれぞれ高々1回しか行わないため、全体の計算量は O(n) です。
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n) の保証：各要素が高々1回ずつ push と pop される理由
単調スタックアルゴリズムが O(n) 時間で動作する理由は、単純な償却計算によって説明できます。各要素はスタックにちょうど1回 push され、pop は高々1回です。どの要素も、1回を超えて push または pop されることはありません。したがって、ループ全体での push と pop の操作回数は最大でも 2n 回となり、ネストした while ループが O(n²) であるかのように見えても、全体の処理量は O(n) です。
この償却計算による分析は、面接で説明する際に重要です。while ループが各反復で n 回実行されるわけではありません。待機していた要素を pop するのに必要な回数だけ実行され、pop された要素はその後二度と戻らないのです。
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2n単調スタック問題の見分け方
最も近い、より大きい要素またはより小さい要素、価格のスパン、一列に並んだ要素のうち見える要素、またはヒストグラムを利用した面積を求める問題では、単調スタックが必要になる可能性があります。次のようなキーワードやパターンに注目してください。各要素について、一方向（左または右）にある関連要素のうち、最も近い要素から答えを求める問題です。
単純な解法で各要素から左または右へ走査すると O(n²) になる場合は、その走査を単調スタックに置き換えます。スタックは答えの候補を保持し、不要な候補を破棄し、必要な瞬間に正しい答えを pop します。
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、単調スタックは、push する前に不変条件に違反する要素を pop することで、増加または減少の順序を維持すること、単調減少スタックは次または前のより大きい要素を求め、単調増加スタックは次または前のより小さい要素を求めること、そして各要素は push と pop を高々1回ずつしかされないため、全体の計算量は O(n) であり O(n²) ではないことを学びました。次は、単調スタックを使ってヒストグラム内の最大長方形を求めます。
よくある質問
「単調スタック：増加と減少」レッスンは無料ですか？
はい。「単調スタック：増加と減少」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「単調スタック：増加と減少」で何を学びますか？
増加スタックまたは減少スタックを維持し、next-greater-elementとprevious-smaller-elementのクエリにO(n)で効率的に答えます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「単調スタック：増加と減少」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。