【算法】队列总结

一、前言

队列（queue）： 简单的数据结构，先进先出的逻辑顺序。

1. 进队操作：

1. 出队操作：

队列常用于跟树的层序遍历（BFS）：

void traverse(TreeNode root) {
    if (null == root) return;
    
    // 初始化队列，将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        
        // 层级遍历代码
        System.out.println(root.val);
        
        if (cur.left != null) q.offer(cur.left);
        if (cur.right != null) q.offer(cur.right);
    }
}

刷题必知操作：

// 创建队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(e); // 入队
queue.add(e);   // 入队
queue.poll();   // 出队

// 优先队列：最小堆（默认）
Queue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
// 优先队列：最大堆
Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
// 自定义排序：最小堆
Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);

二、题目

（1）二叉树的 Z 字形遍历（中）

LeetCode 103

题干分析

这个题目说的是，给你一棵二叉树，要求你从根节点到叶子节点一层一层地进行 Z 字形遍历，也就是先从左向右访问一层节点，然后从右向左访问下一层节点。以这样的方式交替去访问二叉树上每一层节点，并且将访问的结果以二维数组的形式返回。

比如说，给你的二叉树是：

  1
 / \
2   4
   / \
  8  16

它的 Z 字形遍历结果是：

[
 [1],
 [4, 2],
 [8, 16]
]

思路解法

思路：BFS + 变量（判断层次遍历方向）

AC 代码：

// Time: O(n), Space: O(n), Faster: 76.84%
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

    if (null == root) return Collections.emptyList();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    List<List<Integer>> result = new ArrayList<>();
    boolean right2Left = false;  // 判断是否变换方向
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> subResult = new ArrayList<>(size);
        for (int i = 0; i < size; ++i) {
            TreeNode node = queue.poll();
            subResult.add(node.val);
            if (null != node.left) queue.add(node.left);
            if (null != node.right) queue.add(node.right);
        }
        if (right2Left) Collections.reverse(subResult);
        right2Left = !right2Left;
        result.add(subResult);
    }
    return result;
}

（2）任务调度（中）

LeetCode 621

题干分析

这个题目说的是，给你一个字符数组和一个非负整数 n。字符数组表示等待 CPU 处理的任务，每个任务用 A 到 Z 中的一个字符表示，并且每个任务都可以在一个时间单位内完成；n 表示冷却时间，即相同任务之间需要间隔至少 n 个时间单位才能再次执行，冷却时间内的每个时间单位，可以选择执行不同的任务或是让 CPU 处于闲置状态。

现在你要重新组织任务的执行顺序，并计算出最少需要多少个时间单位才能完成所有任务。

# 比如说，给你的任务数组是：
A, A, A, B, B, B, D

# 给你的冷却时间是：
n = 2

# 完成所有任务最少需要 8 个时间单位，一种执行序列是：
A, B, D, A, B, _, A, B

序列中的 '_' 表示 CPU 处于闲置状态。

因此，对于这个例子，你要返回 8。

按上面栗子，题意是：某任务执行完，要等待 n 时间才能继续执行，但这期间可以执行别的任务。

• 比如 A 执行完，那么后面可以执行 B 、D（或者不执行，空着）

思路解法

思路方法有 二： 最大堆 和 数学方法。

方法一：最大堆

1. 统计每个任务数量： 可以存在一个数组里 int[] freqs = new int[26]; （26个字母）。
2. 构建最大堆： 将统计完的数据放入堆中。
3. 计算结果两个变量： ans = result - idle
   • result：每次加分组值（n + 1）
   • idle：最后一个分组有几个空闲
4. 遍历最大堆： 每次取 n + 1 个数，并 -1

时间复杂度计算：O(m) × log(26) => O(m)

• 假设：要处理任务个数 m

• 有 26 种字母，最大堆每次操作时间复杂度 log(26)

  log(26) < 5 可以忽略。

AC 代码：

// 方法一：最大堆
// Time: O(m), Space: O(1), Faster: 35.62%
public int leastIntervalMaxHeap(char[] tasks, int n) {
    if (tasks == null || tasks.length == 0) return 0;

    // 1. 统计每个任务数量
    int[] freqs = new int[26];
    for (char t : tasks) ++freqs[t - 'A'];

    // 2. 构建最大堆
    Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
    for (int freq : freqs) {
        if (freq != 0) q.add(freq);
    }

    // 3. 遍历最大堆
    int result = 0, idle = 0; // idle：最后一个分组有几个空闲
    while (!q.isEmpty()) {
        result += (n + 1);
        idle = n + 1 - q.size();
        int size = Math.min(n + 1, q.size());
        for (int i = 0; i < size; ++i) {
            freqs[i] = q.poll() - 1;
        }
        for (int i = 0; i < size; ++i) {
            if (freqs[i] != 0) q.add(freqs[i]);
        }
    }
    return result - idle;
}

方法二：数学方法

1. 统计每个任务数量： 可以存在一个数组里 int[] freqs = new int[26]; （26个字母）。
2. 任务出现次数最多： maxFreq
3. 有多少个maxFreq： cnt
4. 计算公式： MAX((maxFreq - 1) * (n + 1) + cnt, tasks.len)

AC 代码：

// 方法二：数学方法
// Time: O(m), Space: O(1), Faster: 100.00%
public int leastIntervalMath(char[] tasks, int n) {
    if (tasks == null || tasks.length == 0) return 0;

    // 1. 统计每个任务数量
    int[] freqs = new int[26];
    for (char t : tasks) ++freqs[t - 'A'];

    // 2. 求 maxFreq 和 cnt
    // maxFreq: 任务出现次数最多
    // cnt: 有多少个 maxFreq
    int maxFreq = 0, cnt = 0;
    for (int freq : freqs) {
        if (freq > maxFreq) {
            maxFreq = freq;
            cnt = 1;
        } else if (freq == maxFreq) {
            ++cnt;
        }
    }

    // 3. 计算
    int result = (n + 1) * (maxFreq - 1) + cnt;
    // 取最大值
    return Math.max(result, tasks.length);
}