单调队列

/*
维护的是前k个中最大的数和它的下标
最大数为front()；
*/
class Deque{
public:
    deque<int>a;
    deque<int>id;
    int k;
    bool empty(){
        return a.empty();
    }
     void pop(int i){//弹首
         while(!id.empty()&&id.front()+k<i){//越界了就弹出
             a.pop_front();
             id.pop_front();
         }
     }
    void push(int x,int i){// x 数 i 下标
        while(!a.empty()&&a.back()<x){
            a.pop_back();id.pop_back();
        }
        a.push_back(x);
        id.push_back(i);
        pop(i);
    }
};