给定一个数组，设置一个窗口长度，需要求出每个窗口内的最大值或最小值，暴力做法将会是数组长度乘以窗口长度的时间复杂度。如果使用单调队列，将会是数组长度的线性时间复杂度。本文将对单调队列有一个具体的阐述。
本文封面由Power Point绘制，代码由gemini编写。
算法流程
单调队列能够高效地解决“滑动窗口最大值或最小值”这一类问题，具体可以归结为两种经典应用场景：在固定大小的滑动窗口内动态求解最大值，以及求解最小值。由于这两种场景在实现逻辑上具有高度的对称性，其核心思想完全一致，区别仅在于维持队列内单调性的比较逻辑不同。因此，为了让讲解更加聚焦和深入，本文将只剖析“滑动窗口最大值”这一种情况，当你完全掌握它之后，求解最小值便能轻松地触类旁通。
算法的流程是，我们从左到右遍历数组，并借助一个双端队列来维护一个索引序列，该序列对应的元素值从队头到队尾呈严格单调递减。对于每一个新到来的元素 $nums[i]$，我们首先从队尾开始处理：如果新元素大于或等于队尾索引所对应的元素，则说明队尾元素已不再可能成为未来任何窗口的最大值，因此将其从队尾弹出，并用新元素继续与新的队尾比较，如此循环。此过程结束后，我们将当前元素索引 $i$ 压入队尾。与此同时，我们从队头检查，如果队头元素的索引已经滑出了当前窗口的范围（即索引小于 $i – k + 1$），则将其从队头弹出。完成这些维护操作后，只要窗口已完全形成（即 $i \ge k – 1$），此时的队头索引所对应的元素，就一定是当前窗口的最大值。算法流程图如下所示。
理论推导
算法正确性
算法的正确性源于其巧妙地维护了队头元素的两个关键属性：它始终位于当前窗口内，且必然是窗口内的最大值。确保其在窗口内是通过队头检查实现的：任何滑出窗口左边界（索引小于 $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;
}