POJ 2823 Sliding Window：單調隊列 O(n) 求滑動窗口最大/最小值

題目大意

給定長度 n ≤ 10⁶ 的數組和窗口大小 k，窗口從左向右滑動，每次移動一位。輸出每個窗口位置的最小值和最大值。

樣例：

數組：[1 3 -1 -3 5 3 6 7], k=3
窗口最小值：-1 -3 -3 -3 3 3
窗口最大值：3 3 5 5 6 7

核心算法：單調隊列

思想：維護一個單調遞增（求最小）或單調遞減（求最大）的隊列，隊列存儲數組下標。

維護最小值隊列（單調遞增）

1. 新元素 a[i] 入隊前，從隊尾彈出所有 ≥ a[i] 的元素（它們不可能再成為最小值）
2. 將 i 入隊
3. 若隊首下標 ≤ i-k（滑出窗口），彈出隊首
4. 隊首即為當前窗口最小值下標

維護最大值隊列（單調遞減）

同理，彈出隊尾所有 ≤ a[i] 的元素。

AC 代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000000 + 10;
int q[MAXN], a[MAXN];
int n, k;

void solve() {
    // --- 求最小值 ---
    int front = 0, rear = 0;
    q[++rear] = 1;  // 1-based 下標
    
    for (int i = 1; i <= n; ++i) {
        // 1. 維護單調遞增：彈出隊尾 ≥ a[i]
        while (front <= rear && a[q[rear]] >= a[i]) --rear;
        q[++rear] = i;
        
        // 2. 彈出滑出窗口的隊首
        while (q[rear] - q[front] + 1 > k) ++front;
        
        // 3. 輸出
        if (i == k) printf("%d", a[q[front]]);
        else if (i > k) printf(" %d", a[q[front]]);
    }
    puts("");
    
    // --- 求最大值 ---
    front = 0; rear = 0;
    q[++rear] = 1;
    
    for (int i = 1; i <= n; ++i) {
        while (front <= rear && a[q[rear]] <= a[i]) --rear;
        q[++rear] = i;
        while (q[rear] - q[front] + 1 > k) ++front;
        if (i == k) printf("%d", a[q[front]]);
        else if (i > k) printf(" %d", a[q[front]]);
    }
    puts("");
}

int main() {
    while (scanf("%d%d", &n, &k) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        solve();
    }
    return 0;
}

關鍵點解析

• 下標 1-based：便於計算窗口長度 q[rear] - q[front] + 1
• 隊列存下標：而非值，方便判斷是否滑出窗口
• 每個元素進隊出隊各一次：攤還 O(1)，總體 O(n)
• 輸出格式：首個無前導空格，後續有空格

複雜度

• 時間：O(n)，n ≤ 10⁶ 輕鬆通過
• 空間：O(n) 隊列與數組

總結

單調隊列是滑動窗口極值問題的標準解法，將暴力 O(nk) 優化至 O(n)。關鍵在於「新元素入隊時淘汰無用元素」與「隊首滑出窗口時彈出」兩條規則，保證隊列始終單調且僅含窗口內候選極值。