题目:
分析:
本题要求三个方法的时间复杂度都是 O(1), 对于 push_back 和 pop_front 都是好实现的
但是对于 max_value, 正常情况下要进行遍历才能获得最大值, 那么如何才能在 O(1) 的时间复杂度下获得最大值?
O(1) 时间复杂度意味着直接便可以获得最大值, 一开始的想法是设置两个变量, 一个最大值 max, 一个第二大值 max_2, 每次 push_back 时进行更新, 若 pop_front 的值与最大值相同, 便让 max = max_2
但这样有个问题, 当连续两次 pop_front, 同时前两大的数字都被 pop 出去时, max 与 max_2 存储的值都是错误的, 如果要重新确定 max 与 max_2 的值, 又要进行遍历了
后来看了题解, 里面提到维护一个排序队列 (双向), 当一个元素 cur 插入时, 它前面所有比它小的值都不会对最大值有影响, 而比它大的已经出队了, 因为正常出队时, 出到 cur 时, 它前面的所有值已全部出队, 所以插入时更新双向排序队列, 只保留比当前值大的值的有序队列, 便可以直接取到 max_value, 同时不必担心连续出队导致的找不大最大值, 如果出队的值真好是当前的最大值, 只需要将双向队列的队头出队即可
至于为何时间复杂度为 O(1), 题解中提到:
我的理解是, 在插入时, 会将小于当前值的值出队, 不过这个出队的操作次数是有限的, 一个插入操作最多只有 n 个出队操作, 更多的情况是小于 n 个操作, 也就是说 n 个插入操作总共进行了 n 次出队, 平均下来就是 O(1) 的复杂度
代码:
- class MaxQueue {
- queue<int> que;
- deque<int> deq;
- public:
- MaxQueue() {
- }
- int max_value() {
- if(deq.empty()) return -1;
- return deq.front();
- }
- void push_back(int value) {
- while(!deq.empty() && deq.back()<value)
- deq.pop_back();
- deq.push_back(value);
- que.push(value);
- }
- int pop_front() {
- if(que.empty()) return -1;
- int res = que.front();
- que.pop();
- if(res == deq.front()) deq.pop_front();
- return res;
- }
- };
- /**
- * Your MaxQueue object will be instantiated and called as such:
- * MaxQueue* obj = new MaxQueue();
- * int param_1 = obj->max_value();
- * obj->push_back(value);
- * int param_3 = obj->pop_front();
- */
来源: https://www.cnblogs.com/ech2o/p/12433647.html