POJ 2823：滑動窗口最值 - 單調隊列 O(n) 模板題

POJ 2823：給定長度 n 數組，窗口大小 k，求每個窗口的最小值和最大值。本文介紹單調隊列 O(n) 解法：維護兩個雙端隊列，分別單調遞增（最小值）和單調遞減（最大值）。

單調隊列核心思想

• 隊列存儲數組下標（而非值），便於判斷是否滑出窗口。
• 最小值隊列：隊首為當前窗口最小值下標，隊列內下標對應值單調遞增。
• 最大值隊列：隊首為當前窗口最大值下標，隊列內下標對應值單調遞減。

操作流程（以最小值隊列為例）

1. 入隊：新元素下標 i，從隊尾刪除所有 a[tail] >= a[i] 的下標，再推入 i。
2. 出隊：若隊首下標 ≤ i - k（滑出窗口），彈出隊首。
3. 取值：隊首下標對應值即為窗口最小值（i ≥ k-1 時）。

完整代碼（C++）

#include <cstdio>
#include <deque>
using namespace std;

const int MAXN = 1000010;
int a[MAXN];
int minAns[MAXN], maxAns[MAXN];

int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) == 2) {
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

        deque minQ, maxQ;
        int minCnt = 0, maxCnt = 0;

        for (int i = 0; i < n; ++i) {
            // 最小值隊列：單調遞增
            while (!minQ.empty() && a[minQ.back()] >= a[i]) minQ.pop_back();
            minQ.push_back(i);
            if (minQ.front() <= i - k) minQ.pop_front();
            if (i >= k - 1) minAns[minCnt++] = a[minQ.front()];

            // 最大值隊列：單調遞減
            while (!maxQ.empty() && a[maxQ.back()] <= a[i]) maxQ.pop_back();
            maxQ.push_back(i);
            if (maxQ.front() <= i - k) maxQ.pop_front();
            if (i >= k - 1) maxAns[maxCnt++] = a[maxQ.front()];
        }

        for (int i = 0; i < minCnt; ++i) {
            if (i) printf(" ");
            printf("%d", minAns[i]);
        }
        printf("\n");
        for (int i = 0; i < maxCnt; ++i) {
            if (i) printf(" ");
            printf("%d", maxAns[i]);
        }
        printf("\n");
    }
    return 0;
}

手寫數組版（競賽常用，無 STL 開銷）

int minQ[MAXN], maxQ[MAXN];
int minHead=0, minTail=0, maxHead=0, maxTail=0;

for (int i = 0; i < n; ++i) {
    while (minHead < minTail && a[minQ[minTail-1]] >= a[i]) --minTail;
    minQ[minTail++] = i;
    if (minQ[minHead] <= i - k) ++minHead;
    if (i >= k-1) minAns[minCnt++] = a[minQ[minHead]];

    while (maxHead < maxTail && a[maxQ[maxTail-1]] <= a[i]) --maxTail;
    maxQ[maxTail++] = i;
    if (maxQ[maxHead] <= i - k) ++maxHead;
    if (i >= k-1) maxAns[maxCnt++] = a[maxQ[maxHead]];
}

複雜度分析

• 每個下標最多入隊一次、出隊一次 → 總操作 O(n)。
• 空間 O(k) 隊列 + O(n) 答案數組。

關鍵細節

1. 存下標而非值：判斷滑出窗口需比較位置。
2. 單調性方向：最小值隊列遞增（隊首最小），最大值隊列遞減（隊首最大）。
3. 邊界條件：i - k 為滑出窗口的最大下標（0-based）。
4. 輸出格式：空格分隔，行末無多餘空格，換行。

總結

單調隊列是「滑動窗口最值」的標準解法，將暴力 O(nk) 優化至 O(n)。核心不變量：隊列內下標對應值單調，隊首為窗口最值。掌握「入隊維護單調、出隊檢查過期、隊首取值」三步驟，可解決所有滑動窗口最值/最小/最大/中位數（配合雙堆）問題。