滑动窗口与单调队列：维护极值的 O(N) 艺术

从暴力窗口到单调队列

在长度为 $N$ 的数组中，求每个大小为 $K$ 的滑动窗口内的最大值/最小值，是一个极具代表性的经典问题。 如果每个窗口都暴力遍历 $K$ 个元素，总时间复杂度为 $O(N\times K)$。若 $K$ 达到 $10^5$ 级别，计算量将无法承受。

如果使用平衡树或优先队列（堆），查询极值是 $O(1)$，但元素移出窗口时难以即时删除，即便采用延迟删除，单次调整也是 $O(\log K)$，总时间 $O(N\log K)$。

单调队列则能将总时间压缩至严格的 $O(N)$，每个元素均摊 $O(1)$。

核心哲学：双重单调性与及时淘汰

单调队列之所以能做到 $O(N)$，源自一个生动的直觉：

“如果一个新元素不仅比你年轻（下标更大、生命周期更长），而且能力还比你强（数值更大），那么你就永远不可能成为窗口的最大值，必须立即被淘汰。”

在双端队列（std::deque 或数组模拟双端队列）中，我们存储的是元素的下标：

1. 下标单调递增：越靠后的元素越新，生命周期越长。
2. 数值单调递减（以求最大值为例）：队头始终是当前窗口内最大的元素。

四步标准循环模板

处理每个新进入窗口的元素 $i$ 时，执行标准化流程：

// 假设数组为 nums，求大小为 k 的窗口最大值
std::deque<int> dq; // 存储数组下标
std::vector<int> result;

for (int i = 0; i < nums.size(); ++i) {
    // 1. 队头过时检查：移出窗口左边界外的过期下标
    while (!dq.empty() && dq.front() <= i - k) {
        dq.pop_front();
    }

    // 2. 队尾优越性淘汰：弹出所有数值 <= 当前元素的尾部下标
    while (!dq.empty() && nums[dq.back()] <= nums[i]) {
        dq.pop_back();
    }

    // 3. 将当前下标入队
    dq.push_back(i);

    // 4. 窗口形成后，队头即为当前窗口的最大值
    if (i >= k - 1) {
        result.push_back(nums[dq.front()]);
    }
}

复杂度与拓展应用

• 时间复杂度：每个数组下标最多进队 1 次、出队 1 次，所有 pop 操作的总次数不超过 $N$，因此均摊时间复杂度为严密的 $O(N)$。
• 空间复杂度：队列内最多保存 $K$ 个元素，空间复杂度为 $O(K)$。
• 拓展演进：
  • 单调栈：针对无过期限制的“下一个更大元素（Next Greater Element）”问题。
  • 单调队列优化 DP：在 $dp[i]={\max }_{i-k\le j<i}\{dp[j]+\dots \}$ 形式的转移方程中，利用单调队列维护决策点，实现状态转移降阶。