Update 0239. 滑动窗口最大值.md

itcharge · itcharge · commit 96a1826ef3c4 · 2022-09-07T18:05:58.000+08:00
diff --git a/Solutions/0239. 滑动窗口最大值.md b/Solutions/0239. 滑动窗口最大值.md
@@ -5,23 +5,51 @@
 
 ## 题目大意
 
-给定一个整数数组 `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]
+```
 
 ## 解题思路
 
-暴力求解的话，二重循环，时间复杂度为 $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. 滑动结束时，输出答案数组。
 
-## 代码
+### 思路 1：代码
 
 ```Python
 class Solution:
@@ -39,3 +67,8 @@ class Solution:
         return res
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times \log_2n)$。
+- **空间复杂度**：$O(k)$。
+
