当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.剑指offer.059.最大队列

LeetCode.剑指offer.059.最大队列

题目描述

《剑指offer》面试题59 - II. 队列的最大值
https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

请定义一个队列并实现函数 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]

示例 2:

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

限制:
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5


相似题目

LeetCode.155.Min Stack 最小栈
LeetCode.剑指offer.059.最大队列


解题过程

最大队列比最小栈要复杂一些,还要求 enQueue, deQueue, getMax 都必须 O(1)
总的思路和最小栈一样,空间换时间,用一个额外的结构保存每个状态的最大值。

假设队列有元素 q1, q2, … , qn ,如果想每次 deQueue 后还能 O(1) 获得最大值,我们需要保存
q1 到 qn 也就是全队列的最大值,
q2 到 qn 的最大值

qn-1 到 qn 的最大值

比如有队列 5,6,1,4,2
我们需要保存:
第1个元素到队尾的最大值 6
第2个元素到队尾的最大值 6
第3个元素到队尾的最大值 4
第4个元素到队尾的最大值 4
第5个元素到队尾的最大值 2
可以用一个 双端队列 Deque 保存以 q1,..,qn 为开头 qn 为结尾的各个子队列的最大值,也就是 6,6,4,4,2

enQueue 入队时怎么处理呢?
入队时还需要保持 Deque 的性质不标,依然保存以 q1,..,qn 为开头 qn 为结尾的各个子队列的最大值
由于队列的 先进先出 FIFO 性质,只要值x入队后,则x前面所有比x小的元素组成的子队列的最大值都会变为x
假如入队值x,则我们只需要 从 Deque 的队尾往前找,把所有小于x的值都替换为x即可,注意等于的要保留
比如上面的例子,假如再入队 3,则 Deque 变为 6,6,4,4,3,3

deQueue 出队时怎么处理?
数据queue 和 Deque 依次从队首出队即可。

可以发现 Deque 有好多重复的元素,其实可以压缩一下,只保存必要的值,比如上面的例子可以只保存 6,4,2,只需要在出队时比较下数据queue和 Deque 的队首元素是否相同,相同时 Deque 也出队

private static class MaxQueue {
    // 数据队列
    Queue<Integer> dataQueue;
    // 辅助最大队列
    Deque<Integer> maxQueue;
    public MaxQueue() {
        dataQueue = new LinkedList<>();
        maxQueue = new LinkedList<>();
    }

    public int max_value() {
        // 直接返回 maxQueue 队首
        return maxQueue.isEmpty() ? -1 : maxQueue.peek();
    }

    public void push_back(int value) {
        dataQueue.offer(value);
        // maxQueue 中前面比 value 小的,都可以被value顶替,相等的要保留
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
            maxQueue.pollLast();
        }
        maxQueue.offer(value);
    }

    public int pop_front() {
        if (dataQueue.isEmpty()) {
            return -1;
        }
        int ret = dataQueue.poll();
        // 出队元素只可能小于等于 maxQueue 队首,等于maxQueue队首时 maxQueue 也弹出
        if (maxQueue.peek().equals(ret)) {
            maxQueue.poll();
        }
        return ret;
    }
}

GitHub代码

algorithms/leetcode/offer/_059_MaxQueue.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_059_MaxQueue.java


上一篇 LeetCode.322.Coin Change 零钱兑换

下一篇 LeetCode.剑指offer.057.和为s的连续正数序列

阅读
评论
797
阅读预计3分钟
创建日期 2020-03-07
修改日期 2020-03-07
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论