使用单调双端队列求滑动窗口最大值
维护一个按索引组成的递减双端队列，以对每个元素用 O(1) 时间回答窗口最大值查询，并以 O(n) 时间解决滑动窗口最大值问题。
使用单调双端队列求滑动窗口最大值 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
滑动窗口最大值问题
滑动窗口最大值问题（LeetCode 239）给定一个数组和窗口大小 k。随着窗口从左向右每次移动一个位置，输出每个窗口中的最大元素。暴力方法需要用 O(k) 时间计算每个包含 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）：pop 0（1<3），dq=[1]
- i=2（-1）：-1<3，因此保留，dq=[1,2]。窗口 [1,3,-1]，最大值=nums[1]=3
- i=3（-3）：-3<-1，dq=[1,2,3]。检查队首：1 > 3-3=0，OK。窗口最大值=3
- i=4（5）：pop 3、2、1（都更小），dq=[4]。队首 4 > 4-3=1，OK。最大值=5
- i=5（3）：3<5，dq=[4,5]。队首 4 > 5-3=2，OK。最大值=5
- i=6（6）：pop 5、4（都更小），dq=[6]。最大值=6
- i=7（7）：pop 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)为什么每个元素最多入队和出队一次
O(n) 的保证来自与单调栈相同的摊销分析：每个索引恰好通过 append 一次加入双端队列，并且最多移除一次（要么在过期时从队首移除，要么在被更大元素取代时从队尾移除）。整个循环中的双端队列操作总数最多为 2n。
内层循环不会增加总体复杂度——这些循环中进行的任何弹出操作，都是由之前的入队操作“支付”的。这与单调栈的分析相同，只是扩展到了允许从两端移除元素的双端队列。
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)滑动窗口最小值
滑动窗口最小值是对称的另一种情况：维护一个单调递增双端队列（当新元素小于队尾元素时，从队尾执行 pop）。队首始终保存当前窗口的最小值。其他步骤与最大值版本完全相同，只需反转比较方向。
要求滑动窗口最小值的问题，通常会作为更大算法中的子问题出现。例如，沿一条具有 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]跳跃游戏 VI：使用单调双端队列的 DP
跳跃游戏 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) 的单调双端队列，而不是 O(n log 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 子数组
LeetCode 1493：给定一个二进制数组，找出删除恰好一个元素（可以是 0 或 1）后最长的全 1 子数组长度。这是一个滑动窗口问题。维护一个最多包含一个 0 的窗口。当窗口中有超过一个 0 时，从左侧缩小窗口。
这里使用的是可变大小滑动窗口模式，而不是双端队列。不过，可以将其与最大窗口技巧结合：找到所有有效窗口后，最大长度就是答案。“删除一个元素”意味着我们允许 1 组成的窗口中恰好包含一个 0。
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双端队列、队列与栈的比较
理解何时使用每种容器是面试的关键：
- 栈（列表）：LIFO，只能访问一端。用于 DFS、表达式解析和单调栈问题。
- 队列（使用 appendleft/popleft 的双端队列）：FIFO，一端入队，另一端 pop。用于 BFS 和任务调度。
- 双端队列：两端都可以在 O(1) 时间内访问。用于带过期机制的滑动窗口（从队首移除）以及维护单调不变量（从队尾移除）。滑动窗口最大值是双端队列问题的典型代表。
Python 的 collections.deque 可用于这三种场景。使用 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 的最左侧前缀和。双端队列维护递增的前缀和（从队尾 pop 以保持递增），并从队首 pops 以收集有效答案。
这是最难的滑动窗口问题之一，因为其中包含负数（排除了简单的双指针方法），并且要求双端队列同时充当单调结构和过期机制。
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 递推式 dp[i] = f(nums[i], max(dp[i-k..i-1]))；或者 (3) 需要找到满足单调条件的最近有效索引。
在面试中，请整洁地编写双端队列解法：导入 deque，维护两个不变量（队首过期、队尾单调），并从索引 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))快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学到了：单调递减双端队列在队首维护窗口最大值，同时丢弃从队尾加入且小于新元素的元素，当过期索引超出窗口边界时，从队首将其移除，以及每个索引最多入队和出队一次，因此总体复杂度为 O(n)，双端队列空间复杂度为 O(k)。接下来，我们将同时使用单调栈和双指针方法解决接雨水问题。
常见问题解答
「使用单调双端队列求滑动窗口最大值」课时是免费的吗？
是的 — 「使用单调双端队列求滑动窗口最大值」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「使用单调双端队列求滑动窗口最大值」这节课中我会学到什么？
维护一个按索引组成的递减双端队列，以对每个元素用 O(1) 时间回答窗口最大值查询，并以 O(n) 时间解决滑动窗口最大值问题。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「使用单调双端队列求滑动窗口最大值」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。