第 30 章 单调队列与优先队列 · 知识细节练习

单调队列的定义是？

单调队列主要解决？

判断题：普通队列只在队尾插入；单调队列插入时还从队尾弹出破坏单调性的元素——多一个"尾维护"动作。

判断题：优先队列每次取全局最值；单调队列取"窗口内"最值且还保序——两者用途不同。

单调队列的典型应用是？

单调队列处理滑动窗口的复杂度是？

维护递减队列（求窗口最大），插入新元素时队尾操作是？

判断题：窗口右移后，队头下标若超出窗口左边界则弹出——过期元素必须清除。

单调队列存下标而非值，原因是？

滑动窗口求最大值的完整流程是？

判断题：单调队列常用 deque 实现——需要队头弹（pop_front）与队尾弹（pop_back）两个方向。

判断题：单调队列也可用数组 + 头尾指针模拟（q[head..tail]）——与循环队列类似的技巧。

判断题：单调队列实现三要素 = 尾维护单调、头弹过期、存下标——缺一不可。

滑动窗口问题的描述是？

数组 {1, 3, -1, -3, 5, 3, 6, 7}、窗口 $k = 3$ 的最大值序列是？

同数组窗口 $k = 3$ 的最小值序列是？

判断题：滑动窗口暴力每个窗口扫一遍是 $O(nk)$；单调队列 $O(n)$——$k$ 大时差距巨大。

判断题：滑动窗口框架 = 循环 i 从 1 到 n：弹过期 → 尾维护 → 插入 → i ≥ k 时输出队头。

判断题：滑动窗口变体 = 窗口和（前缀和即可）、窗口最值（单调队列）、窗口计数——按需选工具。

判断题：滑动窗口最值是单调队列的"主场问题"——$O(n)$ 且实现极短。

单调栈的定义是？

单调栈主要解决？

求"下一个更大元素"用递减栈——插入新元素时栈顶操作是？

求"下一个更小元素"用递增栈——判定条件是？

柱状图最大矩形问题的单调栈思路是？

判断题：单调栈与单调队列同是"弹出破坏单调的元素"——差别在容器（栈一端 vs 队列两端+过期）。

判断题：单调栈 $O(n)$ 解决"每个元素两侧最近的最值"类问题——是单调队列的"栈版"。

deque（双端队列）是？

deque 的四端操作是？

判断题：deque 同时具备栈（一端）与队列（另一端）的能力——是两者的超集。

deque 的典型应用是？

判断题：0-1 BFS（边权只有 0 和 1 的最短路）用 deque——0 权边插队头、1 权边插队尾。

判断题：deque 的定位 = "需要两端操作"的场景——单调队列、双端 BFS、滑动窗口。

判断题：priority_queue 默认大根堆（队首最大）、greater 变小根堆——插入删除 $O(\log n)$、取顶 $O(1)$。

延迟删除（lazy deletion）思想是？

判断题：对顶堆 = 大根堆存小半 + 小根堆存大半——动态维护中位数 $O(\log n)$。

判断题：优先队列是贪心算法的标配——"每次取当前最优"的动态场景（合并果子/任务调度/多路归并）。

判断题：优先队列应用总表——top-k、对顶堆中位数、合并果子、Dijkstra、任务调度、多路归并。

判断题：优先队列的价值 = 动态维护"当前最优"——与单调队列的"窗口最值"互补。

单调队列、单调栈、deque、优先队列的总表是？

滑动窗口最大值，选？

判断题：复杂度总表——单调队列/栈 $O(n)$、deque 操作 $O(1)$、优先队列 $O(\log n)$ 单次。

判断题：单调结构（队列/栈）是"线性扫描 + 维护单调"；优先队列是"动态最值"——两类互补。

判断题：应用总表——窗口最值/下一个更大/双端 BFS/top-k/中位数/Dijkstra——四结构各有主场。

需要"每个位置的左侧最近更大元素"，选？

判断题：单调队列忘弹过期队头，窗口外的旧最值会"污染"结果——过期判断是必须的。

判断题：求下一个更大用递减栈（栈顶比当前小才弹）——方向写反（递增栈）会得到错误答案。

判断题：deque 为空时访问 front()/back() 是未定义行为——访问前必须判空。

判断题：延迟删除时每次取顶都要检查"是否已失效"——忘判会把失效元素当真值用。

判断题：以下结论全部正确——"单调队列尾维护+头弹过期+存下标；单调栈递减求下一个更大；deque 空访问非法；延迟删除取顶前判失效"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 5, 3, 4, 2, 1};   // 下标 1 起
05    deque<int> q;                     // 存下标，维护递减
06    for (int i = 1; i <= 5; i++) {
07        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
08        q.push_back(i);
09    }
10    for (int x : q) cout << a[x] << " ";
11    return 0;
12}

单选题：程序输出是？（最终递减队列中的元素值）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();   // 弹过期
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();      // 尾维护
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 k=3 的最大值序列）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();   // 递增队列
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 k=3 的最小值序列）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 9, 8, 7, 6, 5};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 5; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（递减序列的窗口最大值——每个窗口都是递减的，答案恒为窗口左端）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && ______) q.pop_front();       // 弹过期
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：横线处应填入？（使输出为 3 3 5 5 6 7）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[7] = {0, 2, 1, 4, 3, 6, 5};
05    int k = 4;
06    deque<int> q;
07    for (int i = 1; i <= 6; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 k=4 的最大值序列：窗口 [1,4]=4、[2,5]=6、[3,6]=6）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 4, 2, 6, 1, 8, 3, 5};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 7; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 [1,3]=6、[2,4]=6、[3,5]=8、[4,6]=8、[5,7]=8）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 4, 2, 6, 1, 8, 3, 5};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 7; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 [1,3]=2、[2,4]=1、[3,5]=1、[4,6]=1、[5,7]=3）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 3, 1, 4, 1, 5};
05    int k = 2;
06    deque<int> q;
07    for (int i = 1; i <= 5; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 k=2：{3,1}→3、{1,4}→4、{4,1}→4、{1,5}→5）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] >= a[i]) ______;   // 求最小值：弹更大的
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：横线处应填入？（使输出为 -1 -3 -3 -3 3 3）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 8, 3, 5, 2, 7, 1, 9, 4};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 [1,3]=8、[2,4]=5、[3,5]=7、[4,6]=7、[5,7]=9、[6,8]=9）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 长为 n 的数组、窗口 k，暴力 O(nk) vs 单调队列 O(n)
05    int n = 1000000, k = 1000;
06    cout << (long long)n * k;      // 暴力操作量
07    return 0;
08}

单选题：程序输出是？（暴力 10^9 vs 单调队列 10^6 的差距）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 2, 5, 3, 4};   // 下标 1 起
05    stack<int> st;
06    for (int i = 1; i <= 4; i++) {
07        while (!st.empty() && a[st.top()] < a[i]) st.pop();   // 递减栈
08        st.push(i);
09    }
10    vector<int> out;
11    while (!st.empty()) { out.push_back(a[st.top()]); st.pop(); }
12    for (int i = out.size() - 1; i >= 0; i--) cout << out[i] << " ";
13    return 0;
14}

单选题：程序输出是？（从底到顶的递减栈内容）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 2, 1, 5, 3};   // 下标 1 起
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && a[st.top()] < a[i]) {
09            ans[st.top()] = a[i];   // 栈顶的下一个更大 = a[i]
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：程序输出是？（各元素的下一个更大元素，无则为 0：2→5、1→5、5→0、3→0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 4, 2, 5, 1};   // 下标 1 起
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && a[st.top()] > a[i]) {   // 递增栈：栈顶更大则弹
09            ans[st.top()] = a[i];
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：程序输出是？（各元素的下一个更小元素：4→2、2→1、5→1、1→0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 2, 1, 5, 3};
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && ______) {   // 下一个更大：栈顶更小则弹
09            ans[st.top()] = a[i];
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：横线处应填入？（使输出为 5 5 0 0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 6, 4, 8, 2, 5};   // 下标 1 起
05    stack<int> st;
06    for (int i = 1; i <= 5; i++) {
07        while (!st.empty() && a[st.top()] < a[i]) st.pop();
08        st.push(i);
09    }
10    cout << st.size();
11    return 0;
12}

单选题：程序输出是？（处理完后的递减栈大小）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 柱状图最大矩形：heights = {2,1,5,6,2,3}，最大面积 10
05    int h[7] = {0, 2, 1, 5, 6, 2, 3};
06    int n = 6, mx = 0;
07    for (int i = 1; i <= n; i++) {
08        int l = i, r = i;
09        while (l > 1 && h[l - 1] >= h[i]) l--;   // 暴力左右扩展（单调栈加速版同理）
10        while (r < n && h[r + 1] >= h[i]) r++;
11        mx = max(mx, h[i] * (r - l + 1));
12    }
13    cout << mx;
14    return 0;
15}

单选题：程序输出是？（最大矩形面积）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 3, 1, 2, 4};   // 下标 1 起
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && a[st.top()] < a[i]) {
09            ans[st.top()] = a[i];
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：程序输出是？（3→4、1→2、2→4、4→0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    q.push_back(1); q.push_back(2); q.push_front(3);
06    cout << q.front() << " " << q.back() << " " << q.size();
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    q.push_back(1); q.push_back(2); q.push_back(3);
06    q.pop_front();            // 弹 1
07    q.pop_back();             // 弹 3
08    cout << q.front() << " " << q.back();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 3, 1, 4, 1, 5};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 5; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 [1,3]=4、[2,4]=4、[3,5]=5）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    q.push_back(5);
06    ______;                 // 队头插入 1
07    cout << q.front();
08    return 0;
09}

单选题：横线处应填入？（使输出为 1）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 0-1 BFS：0 权边插队头、1 权边插队尾
05    deque<int> q;
06    q.push_back(1);          // 1 权边
07    q.push_front(0);         // 0 权边
08    q.push_back(1);
09    for (int x : q) cout << x << " ";
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    for (int i = 1; i <= 5; i++) q.push_back(i);
06    q.pop_front(); q.pop_front();      // 剩 3 4 5
07    q.push_front(2); q.push_front(1);  // 1 2 3 4 5
08    for (int x : q) cout << x << " ";
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 延迟删除：元素失效不打标记删除，等浮到堆顶再弹
05    priority_queue<int> q;
06    bool valid[10] = {0};
07    q.push(5); valid[5] = true;
08    q.push(3); valid[3] = true;
09    valid[5] = false;                  // 5 失效（不立即删）
10    while (!q.empty() && !valid[q.top()]) q.pop();   // 取顶时清理
11    cout << q.top();
12    return 0;
13}

单选题：程序输出是？（失效的 5 被延迟清理，取到有效的 3）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 对顶堆求中位数：{1,2,3,4,5} 的中位数 3
05    priority_queue<int> maxh;                                    // 小半
06    priority_queue<int, vector<int>, greater<int>> minh;         // 大半
07    int d[5] = {3, 1, 4, 2, 5};
08    for (int i = 0; i < 5; i++) {
09        int x = d[i];
10        if (maxh.empty() || x <= maxh.top()) maxh.push(x);
11        else minh.push(x);
12        if ((int)maxh.size() > (int)minh.size() + 1) { minh.push(maxh.top()); maxh.pop(); }
13        if ((int)minh.size() > (int)maxh.size()) { maxh.push(minh.top()); minh.pop(); }
14    }
15    cout << maxh.top();
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 合并果子：{1,2,9} → 1+2=3（代价 3）→ 3+9=12 → 总 15
05    priority_queue<int, vector<int>, greater<int>> q;
06    int d[3] = {1, 2, 9};
07    for (int x : d) q.push(x);
08    int cost = 0;
09    while (q.size() > 1) {
10        int a = q.top(); q.pop();
11        int b = q.top(); q.pop();
12        cost += a + b;
13        q.push(a + b);
14    }
15    cout << cost;
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int, vector<int>, ______> q;   // 小根堆
05    q.push(3); q.push(1); q.push(2);
06    cout << q.top();
07    return 0;
08}

单选题：横线处应填入？（使输出为 1）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // top-k：{3,1,4,1,5,9,2,6} 最大的 2 个
05    int d[8] = {3, 1, 4, 1, 5, 9, 2, 6};
06    int k = 2;
07    priority_queue<int, vector<int>, greater<int>> q;
08    for (int i = 0; i < 8; i++) {
09        if ((int)q.size() < k) q.push(d[i]);
10        else if (d[i] > q.top()) { q.pop(); q.push(d[i]); }
11    }
12    cout << q.top() << " "; q.pop();
13    cout << q.top();
14    return 0;
15}

单选题：程序输出是？（最大的 2 个从小到大：9、6 的堆内升序输出 6 9？——小根堆弹出顺序 6 9）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // Dijkstra 用优先队列：每次取 dist 最小的未确定点（此处演示取最小逻辑）
05    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
06    q.push({0, 1}); q.push({5, 2}); q.push({2, 3});
07    cout << q.top().first << " " << q.top().second;
08    return 0;
09}

单选题：程序输出是？（dist 最小的点是 0 号距离的 1）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[10] = {0, 2, 9, 4, 7, 1, 8, 3, 6, 5};
05    int k = 4;
06    deque<int> q;
07    for (int i = 1; i <= 9; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（窗口 [1,4]=9、[2,5]=9、[3,6]=8、[4,7]=8、[5,8]=8、[6,9]=8）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 每日温度：{73,74,75,71,69,72} 距下一个更高温的天数
05    int t[7] = {0, 73, 74, 75, 71, 69, 72};
06    int ans[7] = {0};
07    stack<int> st;
08    for (int i = 1; i <= 6; i++) {
09        while (!st.empty() && t[st.top()] < t[i]) {
10            ans[st.top()] = i - st.top();
11            st.pop();
12        }
13        st.push(i);
14    }
15    for (int i = 1; i <= 6; i++) cout << ans[i] << " ";
16    return 0;
17}

单选题：程序输出是？（73→1、74→1、75→0、71→2、69→1、72→0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    // 用 deque 当栈用：push_back + pop_back
06    q.push_back(1); q.push_back(2); q.push_back(3);
07    q.pop_back();
08    cout << q.back();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 任务调度：{3,1,2} 排队接水总等待 = 1+3+6 = 10
05    priority_queue<int, vector<int>, greater<int>> q;
06    q.push(3); q.push(1); q.push(2);
07    long long wait = 0, cur = 0;
08    while (!q.empty()) {
09        cur += q.top(); q.pop();
10        wait += cur;
11    }
12    cout << wait;
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 1, 4, 2, 5, 3};
05    int ans[6] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 5; i++) {
08        while (!st.empty() && a[st.top()] < a[i]) {
09            ______;                 // 记录答案并弹出
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 5; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：横线处应填入？（使输出为 4 5 5 0 0——各元素的下一个更大）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 综合：{2,1,5,6,2,3} 的下一个更大元素
05    int a[7] = {0, 2, 1, 5, 6, 2, 3};
06    int ans[7] = {0};
07    stack<int> st;
08    for (int i = 1; i <= 6; i++) {
09        while (!st.empty() && a[st.top()] < a[i]) {
10            ans[st.top()] = a[i];
11            st.pop();
12        }
13        st.push(i);
14    }
15    for (int i = 1; i <= 6; i++) cout << ans[i] << " ";
16    return 0;
17}

单选题：程序输出是？（2→5、1→5、5→6、6→0、2→3、3→0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) ______;   // 尾维护递减
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：横线处应填入？（使输出为 3 3 5 5 6 7）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, -1, -3, 5, 3, 6, 7};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 8; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        ______;                          // 插入当前下标
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：横线处应填入？（使输出为 3 3 5 5 6 7）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 2, 1, 5, 3};
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && a[st.top()] < a[i]) {
09            ans[st.top()] = a[i];
10            ______;                      // 弹出栈顶
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：横线处应填入？（使输出为 5 5 0 0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    q.push_back(1);
06    q.push_back(2);
07    ______;                  // 弹队头
08    cout << q.front();
09    return 0;
10}

单选题：横线处应填入？（使输出为 2）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int> q;       // 大根堆
05    q.push(3); q.push(5); q.push(1);
06    cout << ______;              // 取堆顶
07    return 0;
08}

单选题：横线处应填入？（使输出为 5）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int> q;
05    bool valid[10] = {0};
06    q.push(5); valid[5] = true;
07    q.push(3); valid[3] = true;
08    valid[5] = false;               // 5 失效
09    while (!q.empty() && ______) q.pop();   // 清理失效堆顶
10    cout << q.top();
11    return 0;
12}

单选题：横线处应填入？（使输出为 3）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 4, 2, 6, 1, 8};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 5; i++) {
08        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (______) cout << a[q.front()] << " ";   // 窗口完整才输出
12    }
13    return 0;
14}

单选题：横线处应填入？（使输出为 6 6 8）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {0, 9, 8, 7, 6, 5};
05    int k = 3;
06    deque<int> q;
07    for (int i = 1; i <= 5; i++) {
08        // 错误：忘了弹过期队头
09        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
10        q.push_back(i);
11        if (i >= k) cout << a[q.front()] << " ";
12    }
13    return 0;
14}

单选题：程序输出是？（递减数组：队头 9 永不被顶掉——忘弹过期后 9 一直"赖"在窗口外输出；正确应为 9 8 7）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {0, 2, 1, 5, 3};
05    int ans[5] = {0};
06    stack<int> st;
07    for (int i = 1; i <= 4; i++) {
08        while (!st.empty() && a[st.top()] > a[i]) {   // 错误：方向反（递增栈）
09            ans[st.top()] = a[i];
10            st.pop();
11        }
12        st.push(i);
13    }
14    for (int i = 1; i <= 4; i++) cout << ans[i] << " ";
15    return 0;
16}

单选题：程序输出是？（方向反算出的是"下一个更小"而非"下一个更大"）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> q;
05    q.pop_front();     // 错误：空 deque 弹出 → 未定义行为
06    cout << "danger";
07    return 0;
08}

判断题：空 deque 上 pop_front()/front() 是未定义行为——操作前必须判 !q.empty()。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int> q;
05    bool valid[10] = {0};
06    q.push(5); valid[5] = true;
07    q.push(3); valid[3] = true;
08    valid[5] = false;
09    // 错误：直接取 top 不检查 valid → 拿到已失效的 5
10    cout << q.top();
11    return 0;
12}

单选题：程序输出是？（漏判失效直接取顶——拿到失效值 5；正确应先清理再取 3）

01#include <bits/stdc++.h>
02using namespace std;
03struct cmp {
04    bool operator()(int a, int b) { return a < b; }   // 错误：想建小根堆却写反
05};
06int main() {
07    priority_queue<int, vector<int>, cmp> q;
08    q.push(3); q.push(1); q.push(2);
09    cout << q.top();
10    return 0;
11}