单调队列

单调队列顾名思义，就是保持一定单调性的队列，他可以访问队头和队尾的元素，只能从队尾添加元素
假设队列的单调性为从队尾到队首单调递增，要保持队列的单调性，在向队尾添加元素时，需要比较队尾元素和要添加的元素(假设为n)的大小关系：

  • 如果队尾元素大于n，那么将n添加到队尾
  • 如果队尾元素小于n，那么将队尾元素弹出，比较n和新的队尾元素的大小关系，循环直至队列为空或者n小于队尾元素为止，将n添加到队尾

那么，这样维护后的队列就是一个单调（递增）队列。

举个例子，将1, 2, 45, 33, 66, 22, 9，逐个添加到单调队列中，看一下最后的队列是什么样子：
单调队列 - 图1

可以见到，最后得到的队列从队尾到队头依次为9,22,66，满足单调递增
用C++来实现一个基于deque的单调队列，代码如下：

  1. class MyQueue
  2. {
  3. public:
  4.     MyQueue() = default;
  5.     //向队尾添加元素
  6.     void push_back(int x)
  7.     {
  8.         // 要保持队列的单调性，需要判断队尾元素的大小
  9.         // 如果队尾元素小于要添加的元素，将队尾元素弹出，循环直到队列为空或者队尾元素大于要添加的元素为止
  10.         while (!dq.empty() && dq.back() < x) {
  11.             dq.pop_back();
  12.         }
  13.         dq.push_back(x);
  14.     }
  16.     // 弹出队头元素
  17.     void pop_front()
  18.     {
  19.         dq.pop_front();
  20.     }
  22.     // 访问队头元素
  23.     int front()
  24.     {
  25.         return dq.front();
  26.     }
  28.     // 访问队尾元素
  29.     int back()
  30.     {
  31.         return dq.back();
  32.     }
  34.     bool empty()
  35.     {
  36.         return dq.empty();
  37.     }
  39. public:
  40.     deque<int> dq;
  42. };
  44. void test01()
  45. {
  46.     vector<int> v{1, 2, 45, 33, 66, 22, 9};
  47.     MyQueue mq;
  48.     for (auto n : v)
  49.     {
  50.         mq.push_back(n);
  51.     }
  53.     while (!mq.empty())
  54.     {
  55.         cout << mq.front() << endl;
  56.         mq.pop_front();
  57.     }
  59. }
  61. int main()
  62. {
  63.     test01(); //输出结果为 66,22,9
  64.     return 0;
  65. }