Update 01.Priority-Queue.md

itcharge · itcharge · commit ee4581333a1a · 2022-09-07T18:05:49.000+08:00
diff --git a/Contents/04.Queue/02.Priority-Queue/01.Priority-Queue.md b/Contents/04.Queue/02.Priority-Queue/01.Priority-Queue.md
@@ -4,9 +4,8 @@
 
 优先队列与普通队列最大的不同点在于 **出队顺序**。
 
-普通队列的出队顺序跟入队顺序相关，符合「先进先出（First in, First out）」的规则。
-
-而优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 **「最高级先出（First in, Largest out）」** 的规则。
+- 普通队列的出队顺序跟入队顺序相关，符合「先进先出（First in, First out）」的规则。
+- 优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 **「最高级先出（First in, Largest out）」** 的规则。
 
 优先队列的示例图如下所示。
 
@@ -16,12 +15,12 @@
 
 优先队列的应用场景非常多，比如：
 
-- 数据压缩：赫夫曼编码算法；
-- 最短路径算法：Dijkstra 算法；
-- 最小生成树算法：Prim 算法；
-- 任务调度器：根据优先级执行系统任务；
-- 事件驱动仿真：顾客排队算法；
-- 选择问题：查找第 k 个最小元素。
+- **数据压缩**：赫夫曼编码算法；
+- **最短路径算法**：Dijkstra 算法；
+- **最小生成树算法**：Prim 算法；
+- **任务调度器**：根据优先级执行系统任务；
+- **事件驱动仿真**：顾客排队算法；
+- **排序问题**：查找第 k 个最小元素。
 
 很多语言都提供了优先级队列的实现。比如，Java 的 `PriorityQueue`，C++ 的 `priority_queue` 等。Python 中也可以通过 `heapq` 来实现优先队列。下面我们来讲解一下优先队列的实现。
 
@@ -197,23 +196,51 @@ class PriorityQueue:
 
 #### 5.1.2 题目大意
 
-给定一个整数数组 `nums`，再给定一个整数 `k`，表示为大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。我们只能看到滑动窗口内的 `k` 个数字，滑动窗口每次只能向右移动一位。
+**描述**：给定一个整数数组 `nums`，再给定一个整数 `k`，表示为大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。我们只能看到滑动窗口内的 `k` 个数字，滑动窗口每次只能向右移动一位。
+
+**要求**：返回滑动窗口中的最大值。
+
+**说明**：
 
-要求：返回滑动窗口中的最大值。
+- $1 \le nums.length \le 10^5$。
+- $-10^4 \le nums[i] \le 10^4$。
+- $1 \le k \le nums.length$。
+
+**示例**：
+
+```Python
+输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
+输出：[3,3,5,5,6,7]
+解释：
+滑动窗口的位置                最大值
+---------------               -----
+[1  3  -1] -3  5  3  6  7       3
+ 1 [3  -1  -3] 5  3  6  7       3
+ 1  3 [-1  -3  5] 3  6  7       5
+ 1  3  -1 [-3  5  3] 6  7       5
+ 1  3  -1  -3 [5  3  6] 7       6
+ 1  3  -1  -3  5 [3  6  7]      7
+
+ 
+输入：nums = [1], k = 1
+输出：[1]
+```
 
 #### 5.1.3 解题思路
 
-暴力求解的话，二重循环，时间复杂度为 $O(n * k)$。
+暴力求解的话，需要使用二重循环遍历，其时间复杂度为 $O(n * k)$。根据题目给定的数据范围，肯定会超时。
 
 我们可以使用优先队列来做。
 
-- 初始的时候将前 `k` 个元素加入优先队列的二叉堆中。存入优先队列的是数组值和索引的元组。优先队列将数组值作为优先级。
-- 然后滑动窗口从第 `k` 个元素开始遍历，将当前数组值和索引的元组插入到二叉堆中。
-- 当二叉堆堆顶元素的索引已经不在滑动窗口的范围中时，即 `q[0][1] <= i - k` 时，不断删除堆顶元素，直到最大值元素的索引在滑动窗口的范围中。
-- 将最大值加入到答案数组中，继续滑动。
-- 最后遍历完输出答案数组。
+##### 思路 1：优先队列
+
+1. 初始的时候将前 `k` 个元素加入优先队列的二叉堆中。存入优先队列的是数组值与索引构成的元组。优先队列将数组值作为优先级。
+2. 然后滑动窗口从第 `k` 个元素开始遍历，将当前数组值和索引的元组插入到二叉堆中。
+3. 当二叉堆堆顶元素的索引已经不在滑动窗口的范围中时，即 `q[0][1] <= i - k` 时，不断删除堆顶元素，直到最大值元素的索引在滑动窗口的范围中。
+4. 将最大值加入到答案数组中，继续向右滑动。
+5. 滑动结束时，输出答案数组。
 
-#### 5.1.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
@@ -231,6 +258,11 @@ class Solution:
         return res
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times \log_2n)$。
+- **空间复杂度**：$O(k)$。
+
 ### 5.2 前 K 个高频元素
 
 #### 5.2.1 题目链接
@@ -239,22 +271,39 @@ class Solution:
 
 #### 5.2.2 题目大意
 
-给定一个整数数组 `nums` 和一个整数 `k`。
+**描述**：给定一个整数数组 `nums` 和一个整数 `k`。
+
+**要求**：返回出现频率前 `k` 高的元素。可以按任意顺序返回答案。
 
-要求：返回出现频率前 `k` 高的元素。可以按任意顺序返回答案。
+**说明**：
+
+- $1 \le nums.length \le 10^5$。
+- $k$ 的取值范围是 $[1, 数组中不相同的元素的个数]$。
+- 题目数据保证答案唯一，换句话说，数组中前 $k$ 个高频元素的集合是唯一的。
+
+**示例**：
+
+```Python
+输入: nums = [1,1,1,2,2,3], k = 2
+输出: [1,2]
+
+
+输入: nums = [1], k = 1
+输出: [1]
+```
 
 #### 5.2.3 解题思路
 
-1. 使用哈希表记录下数组中各个元素的频数。时间复杂度 $O(n)$，空间复杂度 $O(n)$。
+##### 思路 1：哈希表 + 优先队列
+
+1. 使用哈希表记录下数组中各个元素的频数。
 2. 然后将哈希表中的元素去重，转换为新数组。时间复杂度 $O(n)$，空间复杂度 $O(n)$。
 3. 使用二叉堆构建优先队列，优先级为元素频数。此时堆顶元素即为频数最高的元素。时间复杂度 $O(n)$，空间复杂度 $O(n)$。
 4. 将堆顶元素加入到答案数组中，进行出队操作。时间复杂度 $O(log{n})$。
    - 出队操作：交换堆顶元素与末尾元素，将末尾元素已移出堆。继续调整大顶堆。
 5. 不断重复第 4 步，直到 `k` 次结束。调整 `k` 次的时间复杂度 $O(nlog{n})$。
 
-所以总体时间复杂度 $O(nlog{n})$。
-
-#### 5.2.4 代码
+##### 思路 1：代码
 
 ```Python
 class Heapq:
@@ -339,6 +388,11 @@ class Solution:
         return res
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times \log_2n)$。
+- **空间复杂度**：$O(n)$。
+
 ## 参考资料
 
 - 【博文】[浅入浅出数据结构（15）—— 优先队列（堆） - NSpt - 博客园](https://www.cnblogs.com/mm93/p/7481782.html)
