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

---