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

問題描述

長度 n ≤ 10^6 的數組，滑動窗口大小 k，每次右移一位。輸出每個窗口的最小值與最大值。

單調隊列原理

• 維護一個雙端隊列，存儲數組下標，對應值單調遞增 (求最小) 或遞減 (求最大)。
• 新元素入隊時，從隊尾彈出所有不滿足單調性的元素。
• 隊首若超出窗口範圍 (index ≤ i-k) 則彈出。
• 隊首即為當前窗口最值。

二分優化入隊

為了 O(1) 平均，通常用 while 循環彈出隊尾。但也可用二分查找插入位置 (因隊列值有序)，再截斷隊尾，同樣攤還 O(1)。

複雜度

• 時間：O(n) (每個元素進出隊列各一次)。
• 空間：O(k)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
int a[MAXN], qmin[MAXN], qmax[MAXN], vmin[MAXN], vmax[MAXN];
int hmin, tmin, hmax, tmax;
int ansMin[MAXN], ansMax[MAXN];

void push_min(int val, int idx) {
    while (hmin <= tmin && vmin[hmin] <= idx - k) ++hmin;
    int l = hmin, r = tmin;
    while (l <= r) {
        int m = (l+r)>>1;
        if (qmin[m] >= val) r = m-1;
        else l = m+1;
    }
    qmin[++r] = val; vmin[r] = idx; tmin = r;
}
void push_max(int val, int idx) {
    while (hmax <= tmax && vmax[hmax] <= idx - k) ++hmax;
    int l = hmax, r = tmax;
    while (l <= r) {
        int m = (l+r)>>1;
        if (qmax[m] <= val) r = m-1;
        else l = m+1;
    }
    qmax[++r] = val; vmax[r] = idx; tmax = r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    while (cin >> n >> k) {
        for (int i=1;i<=n;i++) cin >> a[i];
        hmin=1; tmin=0; hmax=1; tmax=0;
        for (int i=1;i