0Pricing
Coding Interview Prep · 课时

使用双端队列求滑动窗口最大值

在 O(n) 内维护窗口极值

使用双端队列求滑动窗口最大值 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

滑动窗口最大值

给定一个数组和窗口大小 k，您要在窗口向右滑动时求出每个窗口的最大值。朴素做法需要 O(n 乘以 k)。

更快的保证

使用单调双端队列，您可以在总计 O(n) 的时间内回答所有窗口的问题，只需将数组扫描一次。

再次存储索引

在双端队列中保存索引而不是值。通过索引，您可以检查队首是否已经滑出当前窗口。

from collections import deque
dq = deque()
res = []

保持递减

双端队列中的值从队首到队尾保持按值递减，因此队首索引始终指向窗口最大值。

丢弃较小的队尾元素

添加索引 i 之前，只要队尾对应的 values 更小，就从队尾调用 pop，因为它们不可能成为未来的最大值。

while dq and nums[dq[-1]] <= nums[i]:
    dq.pop()

添加新索引

清除较弱的队尾元素后，将当前索引 append 到队尾。双端队列的顺序会为接下来的步骤保持正确。

dq.append(i)

移除过期的队首

如果队首索引落在窗口之外，就将其 popleft。大小为 k 的窗口从索引 i 减 k 加 1 的位置开始。

if dq[0] <= i - k:
    dq.popleft()

记录每个最大值

当索引为 k 减 1 时形成第一个完整窗口后，双端队列的队首就保存了之后每个位置的答案。

if i >= k - 1:
    res.append(nums[dq[0]])

注意移除顺序

读取答案之前要先移除过期的队首。否则您可能会报告一个已经离开窗口的最大值。

为什么时间是线性的

每个索引最多添加和移除一次，因此双端队列的工作量在每一步中是摊还 O(1)，总体为 O(n)。

最小窗口，同样的思路

要查找滑动窗口的最小值，则让双端队列保持递增。裁剪队尾时，只需反转比较条件。

while dq and nums[dq[-1]] >= nums[i]:
    dq.pop()

快速检查

在滑动窗口最大值问题中，单调双端队列的队首保存什么？

回顾：双端队列解决窗口问题

您维护了一个由索引组成的递减双端队列：裁剪较小的队尾，移除过期的队首，并在每个窗口中读取队首来获得最大值，时间复杂度为 O(n)。🏆

常见问题解答

「使用双端队列求滑动窗口最大值」课时是免费的吗？

是的 — 「使用双端队列求滑动窗口最大值」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「使用双端队列求滑动窗口最大值」这节课中我会学到什么？

在 O(n) 内维护窗口极值 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「使用双端队列求滑动窗口最大值」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 使用栈匹配括号
  2. 单调栈：下一个更大元素
  3. 队列与 collections.deque
  4. 使用双端队列求滑动窗口最大值
← 返回 Coding Interview Prep