# 單調隊列
----
## 能幹嘛
### [Sliding Window](https://zerojudge.tw/ShowProblem?problemid=a146)
給一個長度為 $N$ 的正整數序列 $A$
求每段連續 $k$ 個數中的最大值
> $k<=N<=10^6$
----
### Sample
$N=8$ , $k=3$
$A=$ { $1$ , $3$ , $-1$ , $-3$ , $5$ , $3$ , $6$ , $7$ }
```
[1,3]=3、[2,4]=3、[3,5]=5、[4,6]=5、[5,7]=6、[6,8]=7
```
---
### 暴力啦哪次不暴力
從第 $k$ 個元素跑到第 $N$ 個元素
在第 $i$ 個位置,檢查第 $(i-k+1)$ ~ $i$ 個元素
### 複雜度?
$O(NK)$ ,可以看作 $O(N^2)$
----
### 觀察一下
如果目前看到第 $i$ 個元素
前 $(i-1)$ 個元素中
小於 $A[i]$ 的都不可能再被選到了
----
### Sample Again
$N=8$ , $k=3$
$A=$ { $1$ , $3$ , $-1$ , $-3$ , $5$ , $3$ , $6$ , $7$ }
看到 $A[5]=5$ 的時候,前面 $4$ 個元素都不會再被選到了
---
### 所以呢?
我們維護一個陣列,每項有兩個值
分別代表元素大小及元素位置
滿足:
1. 元素大小遞減
2. 元素位置遞增
----
### 邊看邊想吧~
```cpp=
#include<iostream>
#include<deque>
using namespace std;
const int N=1e6+5;
int n,k,a[N],maxn[N];
deque<pair<int,int> > dq; // first = 元素的大小 、 second = 元素的位置
int main(){
while(cin>>n>>k){
for(int i=0;i<n;i++){
cin>>a[i];
while(dq.size()&&dq.front().second<=i-k) // 刪掉過期的元素
dq.pop_front();
if(dq.size())
maxn[i]=max(dq.front().first,a[i]);
else
maxn[i]=a[i];
while(dq.size()&&dq.back().first<=a[i]) // 刪掉比自己小的元素
dq.pop_back();
dq.push_back(make_pair(a[i],i));
}
for(int i=k-1;i<n;i++) cout<<maxn[i]<<" ";
cout<<endl;
}
}
```
---
## 快樂刷題時間
----
### [108全國賽 水槽](https://judge.tcirc.tw/ShowProblem?problemid=d023)
### [108全國賽 隔離採礦](https://judge.tcirc.tw/ShowProblem?problemid=d088)
### [zerojudge c907 尋找最大矩形](https://zerojudge.tw/ShowProblem?problemid=c907)
{"metaMigratedAt":"2023-06-16T05:07:59.915Z","metaMigratedFrom":"Content","title":"單調隊列","breaks":"true","contributors":"[{\"id\":\"4e4034ad-1ed7-4b73-bb23-29742419b34b\",\"add\":2517,\"del\":791}]"}