记一次腾讯面试，我挂在了最熟悉不过的队列上……

Kamiisa ·

更新时间:2024-09-21

· 842 次阅读

面试官问：你了解队列和链表的区别吗？

我：了解，blabla

面试官又问：你能自己实现队列吗？具体讲讲怎么实现？

我当时说了用链表来实现队列的存储，并实现push和pop的操作，但回答的不具体，面试官有些摇头。今天结合一道力扣题来实现队列

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。

示例 1：
输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

解题思路：双链表实现 max_value()

如果MAXQueueHead == MAXQueueTail 表示队列中没有元素，返回-1。在MAXQueue的头指针的位置保存的就是此时队列中的最大值，直接的取值就可以，时间复杂度是O(1)

push_back():

Queue数组正常的进行添加数据，Queue[QueueTail++] = value;

在进行入队的时候，在MAXQueue中需要进行判断，时间复杂度均摊下来也是O(1)：比value小的值，一定会在value出栈前，先出栈，队列中的最大值最少都是value，就没有保存比value小的值的必要了，MAXQueueTail指向的索引，在数组MAXQueue中还没被赋值，判断的时候需要使用MAXQueueTail-1

MAXQueue[MAXQueueTail-1] < value

pop_front()

Queue中Head的值与 MAXQueue中Head的值相等，则两个数组中的head都要 ++ ，因为最大值已经变了。不然，就是常规的Queue中的head++，时间复杂度是O(1)

解题代码(java)

class MaxQueue { 
    List list; 
    int listHead = 0; 
    int listTail = 0; 
    List MAXlist; 
    int MAXlistHead = 0; 
    int MAXlistTail = 0; 
    public MaxQueue() { 
        list =  new ArrayList(); 
        MAXlist = new ArrayList(); 
    } 
    public int max_value() { 
        if(MAXlistHead == MAXlistTail){ 
            // 头尾相等的时候，表示此时队列为空，没有最大值 
            return -1; 
        } 
        return MAXlist.get(MAXlistHead); 
    } 
    public void push_back(int value) { 
        list.add(listTail++, value); 
        while(MAXlistHead != MAXlistTail && MAXlist.get(MAXlistTail-1) < value){ 
            // MAXlistTail-1 因为MAXlistTail处的值是0，还没有被初始化 
            // 比value小的值，一定会在value出栈前，先出栈， 
            // 队列中的最大值最少都是value，就没有保存比value小的值的必要了 
            MAXlistTail--; 
        } 
        MAXlist.add(MAXlistTail++,value); 
    } 
    public int pop_front() { 
        if(listHead == listTail){ 
            // 队列为空 
            return -1; 
        } 
        int res = list.get(listHead); 
        if(res == MAXlist.get(MAXlistHead)){ 
            MAXlistHead++; 
        } 
        listHead++; 
        return res; 
    } 
}

作者：天才程序媛

腾讯面试面试队列腾讯

1024 个赞