単調デックによるSliding Window Maximum
インデックスの減少デックを維持してウィンドウ内最大値のクエリに要素あたりO(1)で答え、sliding-window-maximum問題をO(n)で解きます。
「単調デックによるSliding Window Maximum」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
スライディングウィンドウの最大値の問題
スライディングウィンドウの最大値の問題（LeetCode 239）では、配列とウィンドウサイズ k が与えられます。ウィンドウを左から右へ一度に1つずつ移動させながら、各ウィンドウ内の最大要素を出力します。全探索では、k 個の要素からなる各ウィンドウの最大値を O(k) で計算するため、全体では O(nk) となり、k が大きい場合には遅すぎます。
単調デック（両端キュー）を使う解法では、インデックスを降順に保ったデックを維持することで、全体を O(n) で処理できます。先頭には常に現在のウィンドウの最大値のインデックスがあるため、O(1) で最大値を取得しながら、先頭と末尾の両方を操作できます。
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))単調デック：重要な考え方
単調減少デックを維持し、値ではなくインデックスを格納します。不変条件は、nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]] です。インデックス i を追加する前に、次の処理を行います：
- 期限切れのインデックスを削除する：先頭の
deque[0] <= i - kが成り立つ場合、そのインデックスはウィンドウの外に出ています。 - 小さいインデックスを削除する：
nums[deque[-1]] <= nums[i]である間、それらのインデックスが将来のどのウィンドウでも最大値になることはありません（新しいインデックスより左側にあり、値も小さいためです）。したがって、それらを破棄します。
これらの処理の後、i を末尾に追加します。先頭には常に現在のウィンドウの最大値があります。
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]デックを手順に沿ってトレースする
k=3 として [1, 3, -1, -3, 5, 3, 6, 7] をトレースしてみましょう：
- i=0 (1)：dq=[0]
- i=1 (3)：0 (1<3) をポップし、dq=[1]
- i=2 (-1)：-1<3 なので保持し、dq=[1,2]。ウィンドウ [1,3,-1]、max=nums[1]=3
- i=3 (-3)：-3<-1、dq=[1,2,3]。先頭を確認すると、1 > 3-3=0 なので問題ありません。ウィンドウの最大値=3
- i=4 (5)：3、2、1 をすべてポップ（すべて小さい）し、dq=[4]。先頭は 4 > 4-3=1 なので問題ありません。最大値=5
- i=5 (3)：3<5、dq=[4,5]。先頭は 4 > 5-3=2 なので問題ありません。最大値=5
- i=6 (6)：5、4 をポップ（どちらも小さい）し、dq=[6]。最大値=6
- i=7 (7)：6 をポップし、dq=[7]。最大値=7
from collections import deque
def sliding_window_max_trace(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
print(f' Remove expired index {dq[0]} from front')
dq.popleft()
while dq and nums[dq[-1]] <= n:
print(f' Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
dq.pop()
dq.append(i)
print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
if i >= k - 1:
win_max = nums[dq[0]]
result.append(win_max)
print(f' Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)各要素がプッシュとポップを最大1回しか行われない理由
O(n) が保証される理由は、単調スタックの場合と同じ償却計算量の考え方にあります。各インデックスはデックにちょうど1回追加され、期限切れになったときに先頭から削除されるか、新しい要素に置き換えられたときに末尾から削除されるかのいずれかで、削除は最大1回です。ループ全体でのデック操作は最大 2n 回です。
内側の while ループが全体の計算量を増やすことはありません。これらのループで行うポップ操作は、それより前のプッシュ操作によってあらかじめ支払われているからです。これは単調スタックと同じ考え方ですが、両端から削除できるデックに拡張したものです。
from collections import deque
def sliding_window_max_instrumented(nums, k):
dq = deque()
result = []
front_pops = back_pops = pushes = 0
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft(); front_pops += 1
while dq and nums[dq[-1]] <= n:
dq.pop(); back_pops += 1
dq.append(i); pushes += 1
if i >= k - 1:
result.append(nums[dq[0]])
print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
return result
import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)スライディングウィンドウの最小値
スライディングウィンドウの最小値は対になる問題です。単調増加デックを維持し、新しい要素が末尾の要素より小さい場合は末尾からポップします。先頭には常に現在のウィンドウの最小値があります。それ以外の手順は最大値の場合と同じで、比較の向きだけを反転します。
スライディングウィンドウの最小値を求める問題は、大きなアルゴリズムの一部として登場することがよくあります。たとえば、k 個の中間地点を含む経路上で物品を移動する最小コストを求める場合、DP 配列に対してスライディングウィンドウの最小値を使うことがあります。
from collections import deque
def sliding_window_min(nums, k):
dq = deque() # increasing monotonic deque
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] >= n:
dq.pop() # pop larger values from back
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # front = min
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3)) # [-1, -3, -3, -3, 3, 3]
from collections import deque
def sliding_window_max(nums, k):
dq = deque(); result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= n: dq.pop()
dq.append(i)
if i >= k-1: result.append(nums[dq[0]])
return result
print('Max k=3:', sliding_window_max(nums, 3)) # [3,3,5,5,6,7]Jump Game VI：単調デックを使った DP
Jump Game VI（LeetCode 1696）は、DP と単調デックを組み合わせる典型的な例です。配列と最大ジャンプ幅 k が与えられ、インデックス 0 から開始します。各ステップでは、1〜k 個先にジャンプし、移動先のセルのスコアを加算します。合計スコアを最大化してください。DP の漸化式は dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]) です。DP 配列に対してスライディングウィンドウの最大値を求めることで、全体を O(n) で処理できます。
このように、各セルが直前の一定サイズのウィンドウ内にあるセルの最大値に依存する DP の漸化式は頻繁に登場し、常に単調デックが必要になります。
from collections import deque
def max_result(nums, k):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices of max dp values in current window
for i in range(1, n):
# Remove expired indices
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max dp in window [i-k, i-1]
dp[i] = nums[i] + dp[dq[0]]
# Maintain decreasing deque on dp values
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[n - 1]
print(max_result([1,-1,-2,4,-7,3], 2)) # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3)) # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2)) # 0スライディングウィンドウの最大値：セグメントツリーによる別解
ウィンドウサイズが固定の k ではなく変化する問題には、単調デックを直接適用できません。その場合は、前処理を O(n log n) で行うことでクエリごとの静的な区間最大値クエリを O(1) で処理できるスパーステーブルか、動的更新に対応し、クエリごとに O(log n) で処理できるセグメントツリーを使います。ただし、k が固定されたスライディングウィンドウでは、O(n) のデックに勝る方法はありません。
面接では、ウィンドウサイズが一定なら、O(n log n) のセグメントツリーよりも O(n) の単調デックを常に優先してください。デックは任意のウィンドウサイズや更新には対応できない一方、セグメントツリーなら対応できるというトレードオフにも触れましょう。
# Sparse table for static RMQ (range maximum query)
import math
def build_sparse_table(arr):
n = len(arr)
LOG = int(math.log2(n)) + 1 if n else 1
table = [[0]*n for _ in range(LOG)]
table[0] = arr[:]
j = 1
while (1 << j) <= n:
for i in range(n - (1 << j) + 1):
table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
j += 1
return table
def query(table, l, r):
k = int(math.log2(r - l + 1))
return max(table[k][l], table[k][r - (1 << k) + 1])
arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result) # [3, 3, 5, 5, 6, 7]1要素削除後の最長連続1の部分配列
LeetCode 1493：二値配列が与えられたとき、要素をちょうど1つ削除した後（削除する要素は 0 でも 1 でもかまいません）の、1だけで構成される最長の部分配列の長さを求めます。これはスライディングウィンドウの問題です。0 を高々1個含むウィンドウを維持し、ウィンドウ内の 0 が2個を超えたら左から縮めます。
これはデックではなく、可変サイズのスライディングウィンドウのパターンを使います。ただし、最大ウィンドウを求めるテクニックと組み合わせ、条件を満たすすべてのウィンドウを調べた後、最大の長さを答えにします。「要素を1つ削除する」という条件により、1だけのウィンドウに 0 をちょうど1個含めることが許されます。
def longest_subarray(nums):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
# Window [left, right] has at most 1 zero
# After deleting one element, length = right - left (not +1, since we delete one)
max_len = max(max_len, right - left)
return max_len
print(longest_subarray([1,1,0,1])) # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1])) # 5
print(longest_subarray([1,1,1])) # 2: must delete one 1デック・キュー・スタックの比較
面接では、それぞれのコンテナをいつ使うかを理解することが重要です：
- スタック（list）：LIFO、片側からアクセスします。DFS、式の解析、単調スタックの問題に使います。
- キュー（appendleft/popleft を持つ deque）：FIFO、一方の端からプッシュし、もう一方の端からポップします。BFS、タスクのスケジューリングに使います。
- デック：両端に O(1) でアクセスできます。期限切れ要素の処理（先頭から削除）と単調性の維持（末尾から削除）が必要なスライディングウィンドウに使います。スライディングウィンドウの最大値は、デックを使う典型的な問題です。
Python の collections.deque は、この3種類すべてに使えるツールです。スタックとして使う場合は append/pop を、キューまたはデックとして使う場合は append/popleft または appendleft/pop を使います。
from collections import deque
# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop()) # 3 (LIFO)
# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft()) # 1 (FIFO)
# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft() # expire front
while dq and nums[dq[-1]] <= n: dq.pop() # maintain back
dq.append(i)
if i >= k - 1:
print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')K以上の和を持つ最短部分配列：デックと累積和
K 以上の和を持つ最短部分配列（LeetCode 862）は、累積和と単調デックを組み合わせる高度な問題です。累積和を作成し、各右端について、prefix[right] - prefix[left] >= k を満たす最も左側の累積和をデックで探します。デックでは累積和を増加順に保ち（増加順を維持するために末尾からポップします）、条件を満たす答えを集めるために先頭からポップします。
これは、負の数が含まれるため単純な二つのポインタが使えず、さらにデックを単調構造と期限切れ処理の両方に使う必要があるため、最も難しいスライディングウィンドウ問題の一つです。
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque() # monotonic increasing deque of indices into prefix
result = float('inf')
for right in range(n + 1):
# Pop from front: valid subarrays ending at `right`
while dq and prefix[right] - prefix[dq[0]] >= k:
result = min(result, right - dq.popleft())
# Pop from back: maintain increasing deque
while dq and prefix[dq[-1]] >= prefix[right]:
dq.pop()
dq.append(right)
return result if result != float('inf') else -1
print(shortest_subarray([1], 1)) # 1
print(shortest_subarray([1, 2], 4)) # -1
print(shortest_subarray([2, -1, 2], 3)) # 3
print(shortest_subarray([84,-37,32,40,95], 167)) # 3デックを使う問題の面接戦略
次の手がかりから、単調デックの問題を見分けてください：(1) 固定サイズのスライディングウィンドウについて最大値または最小値が必要、(2) dp[i] = f(nums[i], max(dp[i-k..i-1])) のような DP の漸化式が必要、または (3) 単調な条件を満たす最も近いインデックスが必要。
面接では、デックの解法を簡潔に実装してください。deque をインポートし、2つの不変条件（先頭での期限切れ処理、末尾での単調性）を維持し、インデックス k-1 から結果を返します。時間計算量が O(n)、デックの空間計算量が O(k)（一度に格納するインデックスは最大 k 個）であることを必ず説明し、O(nk) の全探索と比較して改善点を示してください。
from collections import deque
# Clean, interview-ready template
def sliding_window_max_template(nums, k):
if not nums or k == 0:
return []
dq = deque() # monotonic decreasing, stores indices
result = []
for i in range(len(nums)):
# Invariant 1: remove expired indices (outside window)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Invariant 2: remove indices with smaller values (useless)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Record result once first full window is established
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))クイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認してください。
レッスンのまとめ
このレッスンでは、単調減少デックが先頭でウィンドウの最大値を保持し、新しく追加された要素より小さい要素を末尾から破棄すること、期限切れのインデックスがウィンドウの境界の外に出たときに先頭から削除されること、そして各インデックスはプッシュとポップを最大1回しか行わないため、デックの空間計算量 O(k) で全体の計算量が O(n) になることを学びました。次は、単調スタックと二つのポインタの両方を使って、雨水をトラップする問題を解きます。
よくある質問
「単調デックによるSliding Window Maximum」レッスンは無料ですか？
はい。「単調デックによるSliding Window Maximum」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「単調デックによるSliding Window Maximum」で何を学びますか？
インデックスの減少デックを維持してウィンドウ内最大値のクエリに要素あたりO(1)で答え、sliding-window-maximum問題をO(n)で解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「単調デックによるSliding Window Maximum」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 単調スタック：増加と減少
- ヒストグラム内の最大長方形
- 単調デックによるSliding Window Maximum
- Trapping Rain Water：スタックとTwo-Pointer