LeetCode 剑指 Offer 59 - II. 队列的最大值 单调队列题解，熟悉单调队列，对比滑动窗口最大值题目。

题目

剑指 Offer 59 - II. 队列的最大值

https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/

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

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

思路

题目中已要求时间复杂度需要均摊O(1)，因此暴力解无意义。

前面已经做过 155. 最小栈 以及 239. 滑动窗口最大值，对本题会有一些思路启发。

本题要求方便获取队列的最大值，听起来与 155. 最小栈 类似，均有原始的一个数据结构，然后维护最值。155中我们的基本做法是维护另一个栈，根据写入值与当前最小值的大小关系来决定是否入栈stackMini。此思路同样可以应用在本题。

而 239. 滑动窗口最大值 中，我们的解法二基于单调递减队列，当前写入值更大时，我们会将前序小值出队，保证队列单调递减，也保证了每个元素入队一次、出队一次（均摊时间复杂度O(1)）。

因此本题，我们使用另一个Deque维护一个单调递减队列。

  • push_back ：从队尾入队
    • maxQ空时直接写入新数据
    • maxQ非空：
      • 当前写入值更大时，将队列前序元素一直出队（新加入的一定在更后面被pop_front出队，所以队列最大值==当前写入值）
      • 当前写入值比队尾更小时，直接入队，待后续pop到当前位置为队头时，当前值即为届时的最大值
  • pop_front ：从队头出队
    • queue出队元素等于maxQ队头最大元素时，maxQ队头同步出队

单调队列

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public class MaxQueue {

    /*
     * 执行用时：
     * 25 ms
     * , 在所有 Java 提交中击败了
     * 89.73%
     * 的用户
     * 内存消耗：
     * 49.1 MB
     * , 在所有 Java 提交中击败了
     * 55.59%
     * 的用户
     * 通过测试用例：
     * 34 / 34
     */

    /**
     * 存储队列每项数据
     */
    Queue<Integer> queue;
    /**
     * 存储当前queue对应最大值，单调递减队列
     */
    Deque<Integer> maxQ;

    public MaxQueue() {
        queue = new LinkedList<>();
        maxQ = new LinkedList<>();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!maxQ.isEmpty() && value > maxQ.peekLast()) {
            // 队尾小元素出队
            maxQ.pollLast();
        }
        maxQ.offerLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        // 当前值是最大值时，淘汰一个maxQ最大值元素
        Integer first = queue.poll();
        if (!maxQ.isEmpty() && maxQ.peekFirst().equals(first)) {
            maxQ.pollFirst();
        }
        return first;
    }

    public int max_value(){
        if (maxQ.isEmpty()) {
            return -1;
        }
        return maxQ.peekFirst();
    }
}

复杂度

时间

每个元素入队、出队分别一次，均摊时间复杂度每个元素O(1)，遍历操作（对MaxQueue的push_back、pop_front）队列结构一次，复杂度整体O(n)，每个操作均摊O(1)。

空间

使用了Deque maxQ作为辅助空间，递减序列一直入队的情况下maxQ需要n个元素长度。空间复杂度O(n)。

Ref