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

問題描述

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

單調隊列原理

維護一個雙端隊列，存儲數組下標，保證：

1. 隊列內元素對應的值單調（求最小則遞增，求最大則遞減）。
2. 隊列內下標單調遞增，且都在當前窗口範圍內。

新元素入隊前，從隊尾移除所有不滿足單調性的元素；隊首若超出窗口左邊界則出隊。隊首即為當前窗口的最值。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1111111;
int que[MAXN], num[MAXN], maxn[MAXN], minn[MAXN], idx[MAXN];
int n, k;

void getmin() {
    int fr=1, ed=0;
    for (int i=0; i= num[i]) --ed;
        que[++ed] = num[i]; idx[ed] = i;
    }
    for (int i=k-1; i= num[i]) --ed;
        que[++ed] = num[i]; idx[ed] = i;
        while (idx[fr] < i-k+1) ++fr;
        minn[i-k+1] = que[fr];
    }
}
void getmax() {
    int fr=1, ed=0;
    for (int i=0; i

複雜度
每個元素最多入隊出隊一次，時間 O(n)，空間 O(n)。經典模板題。