[LeetCode] 面试题59 - II. 队列的最大值
Ech2o 人气:0题目：
分析：
本题要求三个方法的时间复杂度都是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();
*/
加载全部内容