Sunday面试指南

滑动窗口最大值怎么求?单调队列为什么能做到 O(n)?

下面是一段模拟面试对话。

🧑‍💻 面试官:窗口每向右移动一格,怎么得到里面的最大值?

🙋‍♂️ 我:记住上一次最大值,再和新进来的数比较。

🧑‍💻 面试官:如果上一次最大值刚好离开窗口呢?

🙋‍♂️ 我:那就重新遍历窗口。

🧑‍💻 面试官:数组严格递减时,每移动一次都要重新遍历。能不能提前保存还可能成为最大值的元素?

单调队列保存的是“仍有机会成为最大值”的候选下标。更小、又更早离开的元素,可以提前淘汰。

面试速答(60 秒版)

我会用一个双端队列保存候选元素的下标,下标从头到尾递增,对应数值从大到小排列。

每加入一个新元素,先从队头移除已经离开窗口的下标,再从队尾移除小于或等于新值的候选,然后把新下标放进去。窗口形成后,队头对应的值就是最大值。

队尾这些旧值更小,而且比新元素更早过期。只要它们还在窗口里,新元素也在,所以它们之后不可能胜过新元素。

每个下标只入队一次、出队至多一次,总时间是 O(n)。队列最多保留一个窗口的候选,辅助空间 O(k)。实现时要用真正支持高效头尾操作的结构,不能在普通数组上反复 shift(),再直接声称 O(n)。

窗口最大值,留下有效候选

知识点详解:为什么可以放心删掉队尾?

先区分两种“删除”

一种是过期删除。窗口右端在 i 时,左端是 i-k+1,比这个位置更早的下标已经不属于窗口,应当从队头移除。

另一种是淘汰删除。新元素进来后,把队尾不大于它的旧元素移除。它们可能还没过期,但已经不值得继续保存。

这两种删除的依据不同。前者检查位置,后者比较数值。只存数值很容易把重复元素和过期位置弄混,因此这里存下标。原题见 LeetCode 239。

用一个具体窗口看候选怎样变化

假设数组是 [4,2,3,1,5],窗口长度为 3。

读到的下标和值操作后的候选下标对应数值已形成窗口的最大值
0,值 4[0][4]尚未形成窗口
1,值 2[0,1][4,2]尚未形成窗口
2,值 3[0,2][4,3]4
3,值 1[2,3][3,1]3
4,值 5[4][5]5

读到 3 时,旧值 2 被淘汰。因为 3 比它大,且出现得更晚,只要 2 还没有离开窗口,3 就一定还在。

再往后,4 离开窗口,先前留下来的 3 就接上了最大值的位置。这正是只保存一个最大值做不到的事。

相等时也可以淘汰旧下标。留下更新的那个,值不变,却能在后续窗口里保留更久。保留相等值也能写对,只是队列规则和代码要一致。

过期删队头,被压过删队尾

TypeScript 用环形数组,Python 用 deque

这里约定 k 是正整数。空数组返回空结果;非空数组要求 k 不大于数组长度。TypeScript 使用容量为 k+1 的环形数组,空出一格区分首尾相等的空队列,避免 shift() 的移动成本。

TypeScript

function maxSlidingWindow(nums: number[], k: number): number[] {
  if (!Number.isInteger(k) || k <= 0) throw new RangeError("invalid k");
  if (nums.length === 0) return [];
  if (k > nums.length) throw new RangeError("k exceeds length");
  const capacity = k + 1;
  const deque = new Array<number>(capacity);
  let head = 0, tail = 0;
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (head !== tail && deque[head] <= i - k) {
      head = (head + 1) % capacity;
    }
    while (head !== tail) {
      const back = (tail - 1 + capacity) % capacity;
      if (nums[deque[back]] > nums[i]) break;
      tail = back;
    }
    deque[tail] = i;
    tail = (tail + 1) % capacity;
    if (i >= k - 1) result.push(nums[deque[head]]);
  }
  return result;
}

Python

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    if type(k) is not int or k <= 0:
        raise ValueError("invalid k")
    if not nums:
        return []
    if k > len(nums):
        raise ValueError("k exceeds length")
    candidates: deque[int] = deque()
    result = []
    for i, value in enumerate(nums):
        while candidates and candidates[0] <= i - k:
            candidates.popleft()
        while candidates and nums[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(i)
        if i >= k - 1:
            result.append(nums[candidates[0]])
    return result

Python 的 deque 官方文档说明了两端追加和弹出的效率。上面的 O(k) 是辅助队列空间,不包含必须返回的答案数组。

两层 while,为什么没有变成 O(nk)?

不能只看到嵌套就把次数相乘。

一个旧下标被队尾淘汰以后,不会再次回来;从队头过期以后,同样不会再被处理。整个过程中,n 个下标各入队一次,各出队至多一次。把所有轮的弹出次数加在一起,最多 n 次。

单独一轮可能弹出很多候选,但后面没有机会反复弹出这些候选。这是摊还分析得到 O(n) 的原因。

面试官继续追问

环形队列,避免反复移动数组

用堆也能做吗?

可以用最大堆保存数值和下标,读取堆顶时清理过期元素。要注意,惰性删除只清理堆顶,其他过期元素可能长期留在堆内,不能未经证明就把空间写成 O(k)。需要额外删除机制或定期重建来控制体积。

单调栈和单调队列怎么区分?

每日温度关心尚未找到更高温度的旧位置,通常只需要操作栈顶。滑动窗口还要从另一端移除过期元素,因此需要双端队列。可以关联 Q683 一起比较。

哪些输入最容易暴露错误?

严格递增、严格递减、所有元素相同、负数、k 为 1、k 等于数组长度。短数组可以直接枚举每个窗口求最大值,和优化版本逐项比较。

面试速记卡

  • 队列存下标,方便同时判断过期和比较数值。
  • 队头删除过期元素,队尾删除被新值压过的旧候选。
  • 新元素更大且更晚过期,旧候选才可以永久淘汰。
  • 每个下标入队一次、出队至多一次,总时间 O(n)。
  • 辅助空间 O(k),实现不能偷偷引入线性队头删除。

公司面试真题

真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。

  • 百度 · 大数据研发 · 校招秋招

    怎样求滑动窗口最大值,并将优先队列解法优化为单调队列?(题意整理)

    百度-大数据研发工程师面经 ↗
    正文记录 8 月 22 日三面结束;原帖发布于 2023-08-22

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历