【LeetCode】剑指 Offer Ⅱ 第7章：队列（6道题） -- Java Version

题库链接：https://leetcode.cn/problem-list/e8X3pBZi/

队列：先入先出，因此新的元素只能添加到队列的尾部，同时只能删除位于队列最前面的元素；
Java 中 Queue 的常用操作：

• add(e) / offer(e)：插入元素；
• remove() / poll()：删除元素；
• element() / peek()：返回最前面的元素；

……
在 Java 中实现接口 Queue 的常用类型有：LinkedList、ArrayDeque 以及 PriorityQueue，但 PriorityQueue 并不是真正的队列，而是堆。

---

1. 剑指 Offer II 041. 滑动窗口的平均值 – P111

给定一个窗口大小和一个整数数据流，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

1.1 队列：滑动窗口 – O(1)（⭐）

时间复杂度 $O(1)$，空间复杂度 $O(n)$

PS：常见实现滑动窗口的方法除了队列之外，还可以实现数组 + 双指针的方式实现，相关内容可参考：【LeetCode】剑指 Offer Ⅱ 第2章：数组（8道题） – Java Version

class MovingAverage {

    ArrayDeque<Integer> deque;  // 队列
    int capicity;  // 容量大小
    int sum;  // 滑动窗口累加和

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        deque = new ArrayDeque<>();
        capicity = size;
        sum = 0;
    }
    
    public double next(int val) {
        if (deque.size() >= capicity) {  // 窗口已满，删除一个再加入一个
            int val2 = deque.poll();
            deque.offer(val);
            sum += val - val2; 
        } else {
            deque.offer(val);  // 窗口未满，直接加入
            sum += val;
        }
        return (double) sum / deque.size();  // 计算当前平均数
    }
}
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */
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

2. 剑指 Offer II 042. 最近请求次数 – P112

写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

2.1 队列：滑动窗口 – O(1)（⭐）

时间复杂度 $O(1)$，空间复杂度 $O(n)$

class RecentCounter {
    ArrayDeque<Integer> deque;
    int windowSize;

    public RecentCounter() {
        deque = new ArrayDeque<>();
        windowSize = 3000;  // 3000ms
    }
    
    public int ping(int t) {    
        deque.offer(t);  // 来就加入
        while (deque.peek() + windowSize < t) {  // 划出范围就出队
            deque.poll();
        }
        return deque.size();
    }
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 剑指 Offer II 043. 在完全二叉树中添加节点 – P115

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的根节点。

3.1 BFS（宽搜）：完全二叉树 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

Key：二叉树的广度优先搜索是从上到下按层遍历二叉树，从二叉树的根节点开始，先遍历二叉树的第1层，再遍历第2层，接着遍历第3层，并以此类推。(通常我们会基于队列来实现二叉树的广度优先搜索)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class CBTInserter {
    ArrayDeque<TreeNode> deque;
    TreeNode root;  // 根节点

    public CBTInserter(TreeNode root) {  // 初始化
        deque = new ArrayDeque<>();
        this.root = root;
        deque.offer(root);
        // 将满状态的节点弹出，并使其孩子节点入队
        while (deque.peek().left != null && deque.peek().right != null) {
            TreeNode node = deque.poll();
            deque.offer(node.left);
            deque.offer(node.right);
        }
    }
    
    public int insert(int v) {  // 插入新节点，并返回新节点的父节点
        TreeNode parent = deque.peek();
        TreeNode node = new TreeNode(v);
        if (parent.left == null) {
            parent.left = node;
        } else if (parent.right == null) {
            parent.right = node;
            deque.poll();  // 弹出已满的父节点，并将其孩子节点入队
            deque.offer(parent.left);
            deque.offer(parent.right);
        }
        return parent.val;
    }
    
    public TreeNode get_root() {  // 返回根节点
        return this.root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */
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

4. 剑指 Offer II 044. 二叉树中每层的最大值 – P119

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

4.1 双队列：按层顺序宽搜 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

Key：如果用广度优先的顺序遍历二叉树时需要区分二叉树的每层，就推荐采用双队列的形式实现：用两个不同的队列 queue1 和 queue2 分别存放两层的节点，队列 queue1 中只存放当前遍历层的节点，而队列 queue1 中只放下一层的节点。（当然，除此之外，我们也可以使用单队列 + 计数器 current | next 的形式来实现同样的效果）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        ArrayDeque<TreeNode> deque1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> deque2 = new ArrayDeque<>();
        int max = Integer.MIN_VALUE;
        List<Integer> res = new ArrayList<>();

        if (root != null) {
            deque1.offer(root);
        }

        while (!deque1.isEmpty()) {
            TreeNode node = deque1.poll();
            max = Math.max(max, node.val);

            if (node.left != null) {
                deque2.offer(node.left);
            }

            if (node.right != null) {
                deque2.offer(node.right);
            }

            if (deque1.isEmpty()) {
                res.add(max);  // 将当前层的最大值保存到结果集
                max = Integer.MIN_VALUE;  // 初始化max
                deque1 = deque2;  // 让 q1 指向 q2
                deque2 = new ArrayDeque<>();
            }
        }
        return res;
    }
}
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

5. 剑指 Offer II 045. 二叉树最低层最左边的值 – P122

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

5.1 双队列：按层顺序宽搜 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

Key，解法基本同上一题，不同的是上一题找的是每层的最大值，本题找的是最低层的最左值，也可以扩展为每层的最左值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        ArrayDeque<TreeNode> deque1 = new ArrayDeque<>();  // 保存当前遍历层的节点
        ArrayDeque<TreeNode> deque2 = new ArrayDeque<>();  // 保存下一层的节点
        deque1.offer(root);  // 加入根节点
        int bottomLeft = root.val;

        while (!deque1.isEmpty()) {
            TreeNode node = deque1.poll();

            if (node.left != null) {
                deque2.offer(node.left);
            }

            if (node.right != null) {
                deque2.offer(node.right);
            }

            if (deque1.isEmpty()) {  // 当前层遍历完毕
                deque1 = deque2;
                deque2 = new ArrayDeque<>();
                if (!deque1.isEmpty()) {
                    bottomLeft = deque1.peek().val;
                }
            }
        }
        return bottomLeft;
    }
}
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

6. 剑指 Offer II 046. 二叉树的右视图 – P123

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

6.1 双队列：按层顺序宽搜 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

Key：本题查找的是每层的最右节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<>();

        ArrayDeque<TreeNode> dq1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> dq2 = new ArrayDeque<>();

        dq1.offer(root);
        List<Integer> list = new ArrayList<>();

        while (!dq1.isEmpty()) {
            TreeNode node = dq1.poll();

            if (node.left != null) {
                dq2.offer(node.left);
            }

            if (node.right != null) {
                dq2.offer(node.right);
            }

            if (dq1.isEmpty()) {  // 此时当前层已经遍历完毕，node即为最右节点
                list.add(node.val);
                dq1 = dq2;
                dq2 = new ArrayDeque<>();
            } 
        }
        return list;
    }
}
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

7. 继续提升：加练题目

🎈 可参考：

• 队列 · SharingSource/LogicStack-LeetCode Wiki · GitHub
• 单调队列 · SharingSource/LogicStack-LeetCode Wiki · GitHub