每日科普 · 2026-10-29 周四

考研 408 × 求职面试

知识点 · 数据结构 · 进阶

双端队列与单调队列

双端队列（deque）支持在队头和队尾两端以 O(1) 插入、删除，可用循环数组或双向链表实现，常用于需要两端操作的场景。
单调队列是双端队列的一种典型应用：队列中元素保持单调递增或递减，用于维护滑动窗口的最值。以求窗口最大值为例，队列通常存下标，新元素入队前从队尾删除所有不大于它的元素，保证队头是当前窗口最大值；同时若队头下标已滑出窗口，就从队头删除。
要点：1. 队列存下标，便于判断过期；2. 每个元素最多入队、出队一次，处理整个数组均摊 O(n)；3. 与优先队列不同，单调队列不维护全序，只保留可能成为答案的候选。

每日一题 · 数据结构

双端队列与单调队列

在滑动窗口最大值问题中，单调队列为什么要从队尾删除所有不大于新元素的下标？

解析

因为这些元素比新元素更早离开窗口，且值不大于新元素，未来不可能成为窗口最大值。删除它们后，队列仍保持单调递减；新元素入队，队头始终是当前窗口最大值。配合过期下标从队头删除，每个下标最多进出一次，总复杂度 O(n)。

面试小贴士 · 数据结构

双端队列与单调队列

面试常问滑动窗口最值、双端队列实现及复杂度。答题先说明存下标、队头过期、队尾维护单调；强调均摊 O(n)。易错：忘记删过期、用值代下标、边界 k=1 或空数组。

代码实现 · C++

代码示例

#include <bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q; // 存下标，队列值单调递减
    vector<int> res;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
        q.push_back(i);
        if (q.front() <= i - k) q.pop_front(); // 队头过期
        if (i >= k - 1) res.push_back(nums[q.front()]);
    }
    return res;
}

int main() {
    vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
    for (int x : maxSlidingWindow(a, 3)) cout << x << " ";
    return 0;
}