# 單調隊列

## 概念
我們直接帶題目
[題目](https://zerojudge.tw/ShowProblem?problemid=a146)
我們像題目一樣想像一個框框
像右一次就pop一個push一個
單調對列也就是用deque儲存這個框框內有可能有利用價值的數
當deque裡的值超出框框就pop掉
有更有利用價值的出現就把前面比較沒有利用價值的的pop掉
這題的利用價值就是數的大或小

假設有兩數a,b，且a比b更有利用價值
如果a比b更右邊出現，那麼當a出現在框框後b就會變得無用
如果b比a更右邊出現，那麼兩數就都還有利用價值

所以越有價值的會在越靠近deque的front的地方(有價值的會從back開始向前一個一個比較並pop，直到遇到更有價值的)

以範測為範例講解(只模擬最大值的)
1 3 -1 -3 5 3 6 7

∣
1 3 -1 -3 5 3 6 7
push 1進來 deque[1]

  ∣
1 3 -1 -3 5 3 6 7
push 3進來 deque[1,3] 3比1大且3是新進的一定比1後面，pop 1 deque[3]

∣    ∣
1 3 -1 -3 5 3 6 7
push -1進來 deque[3,-1] -1比較小但在後面所以留著
ans 3(最前面的)

  ∣     ∣
1 3 -1 -3 5 3 6 7
push -3 pop 1(本來就不在了) deque[3,-1,-3]
ans 3 3
    ∣      ∣
1 3 -1 -3 5 3 6 7
push 5 pop 3 deque[-1,-3,5] 5>3 pop -3, 5>-1 pop -1 deque[5]
ans 3 3 5

       ∣     ∣
1 3 -1 -3 5 3 6 7
push 3 pop -1(本來就不在) deque[5,3]
ans 3 3 5 5

          ∣    ∣
1 3 -1 -3 5 3 6 7
push 6 pop -3(本來就不在) deque[5,3,6] -> deque[5,6]
ans 3 3 5 5 6

            ∣    ∣
1 3 -1 -3 5 3 6 7
push 7 pop 5(本來就不在) deque[6,7]
ans 3 3 5 5 6 7

時間複雜度$O(n)$

以剛剛那題為實作範例
說明在code裡

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
int a[1000005];
signed main(){ios::sync_with_stdio(0);cout.tie(0);
    while(cin >> n >> k){
        if(k > n)k = n;
        memset(a,0,sizeof(a));
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        deque<int> qmax;//存數字在陣列的位置
        deque<int> qmin;//存數字在陣列的位置
        qmax.push_back(0);
        qmin.push_back(0);
        for(int i = 1; i < n; i++){
            //要小心deque是不是空的避免NA
            while(!qmin.empty() && qmin.front() <= i - k){qmin.pop_front();}
            //qmin.front() <= i - k 是判斷有沒有超出框框
            while(!qmin.empty() && a[i] <= a[qmin.back()]){qmin.pop_back();}
            //a[i] <= a[qmin.back()] 是判斷deque內的數有是否還有價值
            qmin.push_back(i);
            if(i >= k - 1){
                cout << a[qmin.front()];
                //當前框框最有價值的就是在front
                if(i < n - 1)cout << ' ';
            }
        }cout << '\n';
        for(int i = 1; i < n; i++){
            //max的和min是一樣的
            while(!qmax.empty() && qmax.front() <= i - k){qmax.pop_front();}
            while(!qmax.empty() && a[i] >= a[qmax.back()]){qmax.pop_back();}
            qmax.push_back(i);
            if(i >= k - 1){
                cout << a[qmax.front()];
                if(i < n - 1)cout << ' ';
            }
        }cout << '\n';
    }
    return 0;
}