# 單調隊列 ---- ## 能幹嘛 ### [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)