单调队列

deque

函数	作用
front()	返回第一个元素的引用
back()	返回最后一个元素的引用
push_front(x)	把元素x插入到双向队列的头部
pop_front()	弹出双向队列的第一个元素
push_back(x)	把元素x插入到双向队列的尾部
pop_back()	弹出双向队列的最后一个元素

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <time.h>
#include <stdlib.h>

using namespace std;
deque <int> s; //构建一个单调递增的单调队列
#define n 100
int main() {
    srand(time(0));
    s.push_back(-1); 
      for (int i = 1; i <= n; i++) {
          int a = rand() % 100;
          while (s.back() > a) s.pop_back();
          s.push_back(a);
      }
      while (s.size() != 1) {
          cout << s.back() << endl;
          s.pop_back();  
    }
  return 0;
}