#创作计划# 单调队列

Srobot

2025-12-28 17:16:12

发布于：广东

3阅读

0回复

0点赞

问题导入：已知一个长度为 $n\ (n≤10^7)$ 的序列 $a$ ，求每一个 $max_{j=i-k+1}^i\ a_j\ (1≤k≤n)$ 。用“暴力”算法的话，时间复杂度为 $O(n*k)$ ，显然是无法接受的，需要优化。

一、单调队列优化

单调队列是一个双端队列，其内元素具有单调性。单调递增用于维护定长区间最小值，单调递减用于维护定长区间最大值。我们以单调递减维护最大值为例，即对于队列内每一个元素 $k_i$ ，满足 $k_1>k_2>...>k_{m-1}>k_m$ ，试着优化开头的问题。
首先，队列初始化为空，顺次扫描整个序列 $a$ 。当扫描到第 $i$ 个元素时：若队列为空，直接将 $a_i$ 加入队列；若队列不为空，判断队列的最后一个元素是否大于 $a_i$ ，若大于则将 $a_i$ 加入队列末尾，反之删除队列最后一个元素，直到队列为空或队列最后一个元素大于 $a_i$ ，将 $a_i$ 加入队列末尾。
解释：若队列最后一个元素不大于 $a_i$ ，则它肯定不会是区间最大值，可以直接删去，因为如果它是区间最大值，则 $a_i$ 肯定也是区间最大值；像这样动态地删去无用数据，以维护队列的单调性，可以减少无效运算，提高算法效率。
输出：如果此时 $i≥k$ ，则需要输出区间最大值。判断队列第一个元素在数组 $a$ 中的下标 $j$ ，若 $j<i-k+1$ ，则代表这是之前的区间最大值，需要删去，重复这一步骤直到 $j≥i-k+1$ ，输出 $a_j$ 即数组 $a$ 在 $[i-k+1,i]$ 中的最大值。
时间复杂度分析：由于每一个元素最多入队及出队一次，因此总时间复杂度为 $O(n)$ 。实际操作时，队列中可以存储下标 $i$ 而非 $a_i$ ，即维护 $a_{k_1}>a_{k_2}>...>a_{k_{m-1}}>a_{k_m}$ ，这样便于判断队列中元素的下标。

二、C++代码实现

按照上述思路编写代码即可。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    int n, k;
    // 输入序列长度 n 和窗口大小 k
    cin >> n >> k;
    vector<int> a(n + 1); // 序列a，下标从1开始
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    deque<int> dq; // 双端队列，用于存储下标，维护单调递减序列

    for (int i = 1; i <= n; i++) {
        // 步骤1：维护队列的单调递减性
        // 当队列非空且队尾下标对应的值 <= 当前值 a[i] 时，队尾元素不可能是后续窗口的最大值，弹出
        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }
        // 将当前下标 i 加入队列
        dq.push_back(i);

        // 步骤2：移除超出窗口范围的队首元素
        // 如果队首元素的下标已经小于当前窗口的左边界 (i - k + 1)，则它已不在窗口内，弹出
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 步骤3：输出窗口最大值
        // 当 i >= k 时，意味着第一个完整的窗口已经形成，可以开始输出
        if (i >= k) {
            // 此时队首元素就是当前窗口 [i-k+1, i] 的最大值的下标
            cout << a[dq.front()] << " ";
        }
    }

    return 0;
}

本人水平有限，如有疑问，欢迎指正！很水的竞赛(邀请码:5ZsC)

有帮助，赞一个

去预览

0/2000

这里空空如也

一、单调队列优化

二、C++代码实现

热门讨论