P1886 滑動窗口 /【模板】單調隊列

題目描述

有一個長為 $n$ 的序列 $a$，以及一個大小為 $k$ 的窗口。現在這個窗口從左邊開始向右滑動，每次滑動一個單位，求出每次滑動后窗口中的最小值和最大值。

例如，對于序列 $[1,3,?1,?3,5,3,6,7]$ 以及 $k=3$，有如下過程：

$$\begin{array}{ccc}\text{窗口位置}& \text{最小值}& \text{最大值}\\ \text{[1???3??-1]?-3???5???3???6???7?}& ?1& 3\\ \text{?1??[3??-1??-3]??5???3???6???7?}& ?3& 3\\ \text{?1???3?[-1??-3???5]??3???6???7?}& ?3& 5\\ \text{?1???3??-1?[-3???5???3]??6???7?}& ?3& 5\\ \text{?1???3??-1??-3??[5???3???6]??7?}& 3& 6\\ \text{?1???3??-1??-3???5??[3???6???7]}& 3& 7\end{array}$$

輸入格式

輸入一共有兩行，第一行有兩個正整數 $n,k$；
第二行有 $n$ 個整數，表示序列 $a$。

輸出格式

輸出共兩行，第一行為每次窗口滑動的最小值；
第二行為每次窗口滑動的最大值。

輸入輸出樣例 #1

輸入 #1

8 3
1 3 -1 -3 5 3 6 7

輸出 #1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

說明/提示

【數據范圍】
對于 $50\%$ 的數據，$1\le n\le 10^5$；
對于 $100\%$ 的數據，$1\le k\le n\le 10^6$，$a_i\in [?2^{31},2^{31})$。

解析：

無法暴力T_T

暴力枚舉的方式是進行 $n?k$ 次循環，每次查找長度為k的區間的最值。這樣的算法的時間復雜度為 $O(n^2)$ ，無法通過本題。

單調隊列

可以建立一個隊列來維護這些數據。這個隊列有一些特點就是：隊列中的數都是原序列 $a$ 中數字 $a_i$ 的下標 $i$ ，隊列隨著窗口滑動而更新，保證隊列中存的下標都處于當前窗口中。并且保持隊首為窗口中最大數的下標。

如何實現

那么如何實現呢？假設我們找每個區間的最小值：將原序列中每個數 $a_i$ 作為一個元素依次進行如下操作：如果隊列為空，直接將當前元素下標 $i$ 入隊。當隊列不為空時，在加入新元素之前，檢查隊尾數 $f$ 代表的原序列數 $a_f$ 是否小于 $a_i$ ，若小于，則將隊尾數刪除，多次判斷，直到隊尾數 $f$ 代表的原序列數 $a_f$ 大于 $a_i$ 或隊列為空。然后將 $i$ 放入隊尾。再檢查隊首數 $s$ ，若 $s$ 已在我們的區間外，則將隊首刪去。則每段區間的最大值就是操作完的隊列的隊首數 $s$ 表示的原序列數 $a_s$

正確性驗證

那么為何這樣實現是正確的呢？因為我們的操作都保證了隊列中的數 $x$ 表示的 $a_x$ 一定是單調遞減的，且 $a_s$ 一定是最大的，當 $a_s$ 不在序列后，隊列中第二個數 $t$ ，一定滿足 $t>s$。雖然 $t$ 與 $s$ 沒有必然的數量關系，但是 $a_{(s+1)\to (t?1)}<a_t<a_s$，也就是說只要 $a_t$ 還在序列，$a_t$ 一定就是最大值！

幾個注意點

但是注意最小值并不是每次操作之后隊尾 $f$ 表示的數 $a_f$ ，因為在之前的操作中可能存在最小值在隊尾，而新判斷的元素 $a_i>a_f$ 導致 $a_f$ 被出隊，$i$ 入隊，而 $a_i$ 并不是區間最小值。所以與求最大值相似，求最小值要條件相反地建一個單調隊列。

由于開始時 $i<k$ ，隊列的變化無法表達整個區間，等到 $i\ge k$ 了，才可以表示第 $i?k+1$ 個區間的最值。

代碼實現

由于兩端都有出隊操作，$STL$ 中的普通隊列 $queue$ 已經無法滿足。所以用 $STL$ 中另一個神奇的雙端隊列 $deque$。

deque相關

deque介紹：

首尾都可插入和刪除的隊列為雙端隊列。

deque聲明：

deque<元素類型> 名稱; 例: deque dq;

deque在本題中可能用到的函數：

• 隊列名.push_back(x); 把x插入隊尾后
• 隊列名.push_front(x); 把x插到隊首
• 隊列名.back(); 返回隊尾元素
• 隊列名.front(); 返回隊首元素
• 隊列名.pop_back(); 刪除隊尾元素
• 隊列名.pop_front(); 刪除隊首元素
• 隊列名.empty(); 判斷雙端隊列是否空
• 隊列名.clear(); 清空雙端隊列

CoDe

代碼與解析基本相符，注釋略。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
int mn[1000005];
int mx[1000005];
deque<int>dq;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){while(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();while(!dq.empty()&&a[dq.back()]>a[i]) dq.pop_back();dq.push_back(i);if(i>=k){mn[i]=a[dq.front()];}}for(int i=k;i<=n;i++){cout<<mn[i]<<' ';}cout<<endl;dq.clear();for(int i=1;i<=n;i++){while(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();while(!dq.empty()&&a[dq.back()]<a[i]) dq.pop_back();dq.push_back(i);if(i>=k){mx[i]=a[dq.front()];}}for(int i=k;i<=n;i++){cout<<mx[i]<<' ';}return 0;
}

當然你用自己手寫的雙向隊列來實現操作也可以，代碼就不放了。我看其他大部分人都是用手寫雙向隊列來實現操作的，代碼很好找。

單點隊列一般不作為單獨題目出現，而是作為動態規劃的一種優化出現在一些較難的動態規劃題中

求贊QAQ