剑指offer-队列最大值

队列最大值

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

若队列为空，pop_front 和 max_value 需要返回 -1

示例

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

思路

两个队列，一个普通队列一个双端队列

入队普通队列直接入队双端队列，查看入队的元素是否比此队列最后一个元素还要小，如果则加入，否则把后面的先出队，直到最后一个元素大于加入的元素，这个时候再添加进去

出队普通队列直接出队如果普通队列的对头与双端队列的对头相等则一起出队

代码

class MaxQueue {
    constructor() {
        this.que = [];
        this.deq = [];
    }
    max_value() {
        return this.deq.length > 0 ? this.deq[0] : -1;
    }
    push_back(val) {
        this.que.push(val);
        while (this.deq.length > 0 && val > this.deq[this.deq.length - 1]) {
            this.deq.pop();
        }
        this.deq.push(val);
    }
    pop_front(){
        if (this.que.length === 0) {
            return -1;
        }
        while (this.que[0] === this.deq[0]) {
            this.deq.shift();
        }
        return this.que.shift();
    }
}

复杂度分析:

时间复杂度: O(1)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

队列最大值

思路

代码

CATALOG

FEATURED TAGS

FRIENDS