单一队列
单调队列
单调队列是指:队列中元素之间的关系具有单调性,而且,队首和队尾都可以进行出队操作,只有队尾可以进行入队操作。
以单调不减队列为例:队列内的元素(e1,e2,e3...en)存在(e1<=e2<=e3<=...<=en)的关系,所以队首元素e1一定是最小的元素。与优先队列不同的是,当有一个新的元素e入队时,先要将队尾的所有大于e的元素弹出,以保证单调性,再让元素e入队尾。
例如这样一组数(1,3,2,1,5,6),进入单调不减队列的过程如下:
1入队,得到队列(1);
3入队,得到队列(1,3);
2入队,这时,队尾的的元素3>2,将3从队尾弹出,新的队尾元素1<2,不用弹出,将2入队,得到队列(1,2);
1入队,2>1,将2从队尾弹出,得到队列(1,1);
5入队,得到队列(1,1,5);
6入队,得到队列(1,1,5,6);
代码实现:
#include <iostream> using namespace std; class MonotonicQueue { #define MAXN 1000000 public: MonotonicQueue(void) { q = new int[MAXN+5]; f = r = 0; } void push(const int val) { while (r > f && q[r-1] > val) //弹出大于新元素的队尾元素 { r--; } q[r++] = val; } int front(void) { if (f < r) { return q[f]; } return 0; } void pop_front(void) { if (f < r) { f++; } } bool isEmpty(void) { return f == r; } void clear(void) { f = r = 0; } ~MonotonicQueue(void) { delete q; } private: int *q; int f; int r; }; int main(void) { MonotonicQueue mq; int n; while (cin >> n) { int i; for (i = 0; i < n; i++) { int a; cin >> a; mq.push(a); } while (!mq.isEmpty()) { cout << mq.front() << endl; mq.pop_front(); } mq.clear(); } return 0; }访问队首和删除队首元素的时间复杂度为O(1),在队尾加入元素的最坏情况下的时间复杂度为O(n),n为队列当前长度。所以,可以采用二分查找,来确定新加入元素应该插入的位置。