面试题库 › C++ / 后端 › 滑动窗口最大值的单调队列解法

滑动窗口最大值的单调队列解法

难度 ★★★在 4 场真实面经中被问到 方向:C++ / 后端考点:栈与队列

哪些公司问过

蔚来2字节跳动1京东1

常见岗位:机器学习算法(泛)、后端开发、软件开发、C/C++ 软件开发

答案要点

  1. 暴力法每个窗口扫描 k 个元素,O(nk)
  2. 用双端队列存下标,保持对应值单调递减,队首即窗口最大值
  3. 先弹出队尾小于当前值的下标,再入队当前下标
  4. 队首下标滑出窗口时从队首弹出
  5. 每个元素最多进出队一次,时间 O(n),空间 O(k)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题