给定一个数组，设置一个窗口长度，需要求出每个窗口内的最大值或最小值，暴力做法将会是数组长度乘以窗口长度的时间复杂度。如果使用单调队列，将会是数组长度的线性时间复杂度。本文将对单调队列有一个具体的阐述。
本文封面由Power Point绘制，代码由gemini编写。
算法流程
单调队列能够高效地解决“滑动窗口最大值或最小值”这一类问题，具体可以归结为两种经典应用场景：在固定大小的滑动窗口内动态求解最大值，以及求解最小值。由于这两种场景在实现逻辑上具有高度的对称性，其核心思想完全一致，区别仅在于维持队列内单调性的比较逻辑不同。因此，为了让讲解更加聚焦和深入，本文将只剖析“滑动窗口最大值”这一种情况，当你完全掌握它之后，求解最小值便能轻松地触类旁通。
算法的流程是，我们从左到右遍历数组，并借助一个双端队列来维护一个索引序列，该序列对应的元素值从队头到队尾呈严格单调递减。对于每一个新到来的元素 $nums[i]$，我们首先从队尾开始处理：如果新元素大于或等于队尾索引所对应的元素，则说明队尾元素已不再可能成为未来任何窗口的最大值，因此将其从队尾弹出，并用新元素继续与新的队尾比较，如此循环。此过程结束后，我们将当前元素索引 $i$ 压入队尾。与此同时，我们从队头检查，如果队头元素的索引已经滑出了当前窗口的范围（即索引小于 $i – k + 1$），则将其从队头弹出。完成这些维护操作后，只要窗口已完全形成（即 $i \ge k – 1$），此时的队头索引所对应的元素，就一定是当前窗口的最大值。算法流程图如下所示。
%%{init:{
"theme":"base",
"themeVariables":{
"background":"transparent",
"primaryColor":"#4facfe",
"primaryTextColor":"#000",
"primaryBorderColor":"#000",
"lineColor":"#000",
"secondaryColor":"#ffecd2",
"tertiaryColor":"#c8e6c9",
"edgeLabelBackground":"#fff",
"clusterBkg":"#fff",
"clusterBorder":"#000",
"defaultLinkColor":"#000",
"titleColor":"#000",
"nodeTextColor":"#000"
}
}}%%
flowchart LR
Start(("开始"))
Init["<b>初始化</b><br/>━━━━━━━━━<br/>空双端队列 dq<br/>结果数组 result<br/>索引 i = 0"]
CheckLoop{"<b>循环条件</b><br/>━━━━━<br/>i < n?"}
CheckFront{"<b>移除过期元素</b><br/>━━━━━━━<br/>dq 非空 且<br/>dq.front() <= i - k?"}
PopFront["从队头弹出<br/>dq.pop_front()"]
CheckBack{"<b>维护单调性</b><br/>━━━━━━<br/>dq 非空 且<br/>nums[i] >= nums[dq.back()]?"}
PopBack["从队尾弹出<br/>dq.pop_back()"]
PushBack["新索引入队<br/>dq.push_back(i)"]
CheckWindow{"<b>窗口检查</b><br/>━━━━━<br/>i >= k - 1?"}
RecordMax["记录最大值<br/>result.push(nums[dq.front()])"]
Increment["索引递增<br/>i = i + 1"]
Return["<b>返回结果</b><br/>━━━━━━<br/>result"]
End(("结束"))
Start ==> Init
Init ==> CheckLoop
CheckLoop ==>|是| CheckFront
CheckLoop ==>|否| Return
CheckFront ==>|是| PopFront
PopFront ==> CheckFront
CheckFront ==>|否| CheckBack
CheckBack ==>|是| PopBack
PopBack ==> CheckBack
CheckBack ==>|否| PushBack
PushBack ==> CheckWindow
CheckWindow ==>|是| RecordMax
RecordMax ==> Increment
CheckWindow ==>|否| Increment
Increment ==> CheckLoop
Return ==> End
style Start fill:#8B5CF6,stroke:#000,stroke-width:3px,color:#fff
style End fill:#EC4899,stroke:#000,stroke-width:3px,color:#fff
style Init fill:#3B82F6,stroke:#000,stroke-width:3px,color:#fff
style CheckLoop fill:#F59E0B,stroke:#000,stroke-width:3px,color:#000
style CheckFront fill:#EAB308,stroke:#000,stroke-width:3px,color:#000
style PopFront fill:#EF4444,stroke:#000,stroke-width:3px,color:#fff
style CheckBack fill:#06B6D4,stroke:#000,stroke-width:3px,color:#000
style PopBack fill:#F97316,stroke:#000,stroke-width:3px,color:#fff
style PushBack fill:#10B981,stroke:#000,stroke-width:3px,color:#fff
style CheckWindow fill:#FBBF24,stroke:#000,stroke-width:3px,color:#000
style RecordMax fill:#14B8A6,stroke:#000,stroke-width:3px,color:#fff
style Increment fill:#A78BFA,stroke:#000,stroke-width:3px,color:#000
style Return fill:#0EA5E9,stroke:#000,stroke-width:3px,color:#fff理论推导
算法正确性
算法的正确性源于其巧妙地维护了队头元素的两个关键属性：它始终位于当前窗口内，且必然是窗口内的最大值。确保其在窗口内是通过队头检查实现的：任何滑出窗口左边界（索引小于 $i – k + 1$）的元素都会被及时移除。而其最大值的地位则可以通过反证法来理解：假设在当前窗口内存在一个比队头元素 $x$ 更大的元素 $y$，那么在 $y$ 当初入队时，根据“从队尾淘汰所有小于等于自己”的规则，更早入队且值更小的 $x$ 必然已经被 $y$ “清算”出队了。这与 $x$ 至今仍是队头的事实相矛盾，因此假设不成立，队头元素必定是当前窗口的最大值。
时间复杂度
由于数组中的每个元素在整个过程中最多入队一次、出队一次，所有操作的总和与元素数量 $N$ 呈线性关系，因此总时间复杂度为 $\mathcal{O}(N)$。
代码实现
#include <iostream>
#include <vector>
#include <deque>
/**
* @brief 使用单调队列解决“滑动窗口最小值”问题
* @param n 数组的大小
* @param k 窗口的大小
* @param a 输入的数组
* @return 一个包含每个窗口最小值的数组
*/
std::vector<int> get_sliding_window_min(int n, int k, const std::vector<int>& a) {
std::vector<int> result;
// 1. 创建一个双端队列，用于存储元素的“索引”。
// 对于最小值问题，队内索引对应的元素值，从队头到队尾保持单调递增。
std::deque<int> dq;
// 2. 从左到右遍历数组
for (int i = 0; i < n; ++i) {
// 3. 维护队头：移除滑出窗口的旧索引 (索引 <= i - k)
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 4. 维护队尾：保持队列的单调递增性
// 当前元素 a[i] 小于等于队尾元素，则队尾元素不再有成为最小值的可能
while (!dq.empty() && a[dq.back()] >= a[i]) {
dq.pop_back();
}
// 5. 新元素的索引入队
dq.push_back(i);
// 6. 记录结果：当窗口完全形成后 (i >= k - 1)，队头即为当前窗口最小值的索引
if (i >= k - 1) {
result.push_back(a[dq.front()]);
}
}
return result;
}
/**
* @brief 使用单调队列解决“滑动窗口最大值”问题
* @param n 数组的大小
* @param k 窗口的大小
* @param a 输入的数组
* @return 一个包含每个窗口最大值的数组
*/
std::vector<int> get_sliding_window_max(int n, int k, const std::vector<int>& a) {
std::vector<int> result;
// 1. 创建一个双端队列，用于存储元素的“索引”。
// 对于最大值问题，队内索引对应的元素值，从队头到队尾保持单调递减。
std::deque<int> dq;
// 2. 从左到右遍历数组
for (int i = 0; i < n; ++i) {
// 3. 维护队头：移除滑出窗口的旧索引 (索引 <= i - k)
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 4. 维护队尾：保持队列的单调递减性
// 当前元素 a[i] 大于等于队尾元素，则队尾元素不再有成为最大值的可能
while (!dq.empty() && a[dq.back()] <= a[i]) {
dq.pop_back();
}
// 5. 新元素的索引入队
dq.push_back(i);
// 6. 记录结果：当窗口完全形成后 (i >= k - 1)，队头即为当前窗口最大值的索引
if (i >= k - 1) {
result.push_back(a[dq.front()]);
}
}
return result;
}
int main() {
// 针对大数据规模，开启快速 I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, k;
std::cin >> n >> k;
// 使用 vector 存储输入
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
// 调用接口函数分别获取最小值和最大值序列
std::vector<int> min_results = get_sliding_window_min(n, k, a);
std::vector<int> max_results = get_sliding_window_max(n, k, a);
// 按格式输出最小值序列
for (size_t i = 0; i < min_results.size(); ++i) {
std::cout << min_results[i] << (i == min_results.size() - 1 ? "" : " ");
}
std::cout << "\n";
// 按格式输出最大值序列
for (size_t i = 0; i < max_results.size(); ++i) {
std::cout << max_results[i] << (i == max_results.size() - 1 ? "" : " ");
}
std::cout << "\n";
return 0;
}