亲宝软件园·资讯

展开

[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();
 */

 

加载全部内容

相关教程
猜你喜欢
用户评论