POJ 2823 滑動窗口最值：單調隊列雙向維護 O(n) 模板

問題描述

長度 n（≤10⁶）數組，窗口大小 k，窗口從左向右滑動。輸出每個窗口的最小值和最大值。

單調隊列核心思想

• 最小值隊列：單調遞增（隊首最小），新元素入隊時彈出隊尾所有 ≥ 它的元素
• 最大值隊列：單調遞減（隊首最大），新元素入隊時彈出隊尾所有 ≤ 它的元素
• 兩隊列同步維護窗口邊界，超出左邊界的隊首彈出

完整代碼

#include 
using namespace std;
const int MAXN = 1000005;

int n, k, a[MAXN];
int q[MAXN], head, tail;
int mn[MAXN], mx[MAXN];

// 最小值隊列：單調遞增
void push_min(int i) {
    while (head < tail && a[i] <= a[q[tail-1]]) --tail;
    q[tail++] = i;
}

// 最大值隊列：單調遞減
void push_max(int i) {
    while (head < tail && a[i] >= a[q[tail-1]]) --tail;
    q[tail++] = i;
}

// 移除超出窗口的元素
void pop(int i) {
    if (q[head] <= i - k) ++head;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> k) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        
        // 求最小值
        head = tail = 0;
        for (int i = 1; i < k; ++i) push_min(i);
        int mcnt = 0;
        for (int i = k; i <= n; ++i) {
            push_min(i);
            pop(i);
            mn[mcnt++] = a[q[head]];
        }
        
        // 求最大值
        head = tail = 0;
        for (int i = 1; i < k; ++i) push_max(i);
        int xcnt = 0;
        for (int i = k; i <= n; ++i) {
            push_max(i);
            pop(i);
            mx[xcnt++] = a[q[head]];
        }
        
        // 輸出
        for (int i = 0; i < mcnt; ++i) {
            if (i) cout << ' ';
            cout << mn[i];
        }
        cout << '\n';
        for (int i = 0; i < xcnt; ++i) {
            if (i) cout << ' ';
            cout << mx[i];
        }
        cout << '\n';
    }
    return 0;
}

關鍵點總結

複雜度

• 時間：O(n)，每個元素進出隊各一次
• 空間：O(n) 存數組與隊列

避坑指南

• 隊列存下標而非值，便於判斷是否過期
• 初始化時先放入前 k-1 個元素
• 輸出格式：每行值間單空格，行末無空格
• 多測試用例，while(cin>>n>>k) 讀至 EOF

擴展應用

• 滑動窗口中位數（雙堆/平衡樹）
• 滑動窗口第 k 小（主席樹/分塊）
• 動態滑動窗口最大值（單調隊列+雙端隊列）