文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 方法一：暴力法
- 方法二：优先队列
- 方法三：单调队列
- 参考文献
1.问题描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
示例 1：
输入：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
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
2.难度等级
Hard。
3.热门指数
★★★★☆
出题公司：阿里、腾讯、字节。
4.解题思路
方法一：暴力法
遍历所有的滑动窗口，通过遍历窗口内的所有值获取窗口最大值。
那一共有多少个滑动窗口呢，小学题目，一共可以得到 n-k+1 个滑动窗口。其中 n 为数组长度，k 为滑动窗口大小。
假设 nums = [1,3,-1,-3,5,3,6,7] 和 k = 3，那么窗口数为 n-k+1 = 6。
时间复杂度： O((n-k+1)k)。
空间复杂度：O(1)。不算结果集占用的内存，使用一个变量表示滑动窗口的最大值，所以空间复杂度为 O(1)。
注意： 该解法在 LeetCode 会「超出时间限制」。
下面以 Golang 为例给出实现。
func maxSlidingWindow(nums []int, k int) []int {
var r []int
for i := k; i <= len(nums); i++ {
max := slices.Max(nums[i-k:i])
r = append(r, max)
}
return r
}
方法二：优先队列
好一些的做法，使用优先队列（堆）来做。
在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。注意堆的左右孩子没有大小的顺序。
我们可以构建维护一个大顶堆，堆顶元素就是滑动窗口中的最大值。每一次窗口滑动的时候，我们都需要将新进入窗口的元素加到堆中。
注意： 因为堆不支持删除指定的元素，删除元素只能将堆顶的元素弹出，所以在移动窗口时，左边离开窗口的元素不着急从堆中删除，而是当堆顶元素不在窗口中时，不断地移除堆顶的元素，直到堆顶的元素出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。
为了方便判断堆顶元素与滑动窗口的位置关系，我们在堆中存储二元组 (num, index)，堆的元素是下标 index，权重是下标对应的值 num。
时间复杂度： 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
空间复杂度： O(n)，即为优先队列需要使用的空间。
下面以 Golang 为例给出实现。
// a 表示数组，用于表示堆中元素的权重。
var a []int
// 堆，需要实现 heap.Interface 接口。
// 使用 []int 作为堆的存储结构，其中存储数组 nums 的下标。
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
// 注意：heap 包的源码在 Pop 前会将堆顶元素与最后一个元素交换后再调用该函数。
func (h *hp) Pop() interface{} { s := h.IntSlice; v := s[len(s)-1]; h.IntSlice = s[:len(s)-1]; return v }
func maxSlidingWindow(nums []int, k int) []int {
a = nums
q := &hp{make([]int, k)}
for i := 0; i < k; i++ {
q.IntSlice[i] = i
}
heap.Init(q)
n := len(nums)
r := make([]int, 1, n-k+1)
r[0] = nums[q.IntSlice[0]]
for i := k; i < n; i++ {
heap.Push(q, i)
// 当堆顶元素不在窗口中时不断弹出，直至堆顶的元素出现在滑动窗口中。
for q.IntSlice[0] <= i-k {
heap.Pop(q)
}
r = append(r, nums[q.IntSlice[0]])
}
return r
}
方法三：单调队列
能不能在线性时间内求解该问题呢？
我们可以通过一个单调队列保存当前窗口的最大值以及「在窗口最大值后面递减的值」。
为了便于判断队首元素是否超出窗口范围，所以队列中保存数组元素下标。
- 首先初始化第一个窗口对应的单调队列。遍历窗口元素：
- 如果大于等于队尾元素，则删除队尾元素，然后将元素下标存入队尾。
- 如果小于队尾元素，则直接入队列。
-
然后获取队首元素作为第一个窗口的最大值。
-
当滑动窗口向右移动时，我们需要把一个新的元素放入队列。放入方式与初始化第一个窗口对应的单调队列相同。
-
每移动一次窗口，都需要判断队首元素下标是否已经不在当前窗口，如果不在则移除。
为了可以同时弹出队首和队尾的元素，我们需要使用「双端队列」。
时间复杂度： O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
空间复杂度： O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)。
下面以 Golang 为例给出实现：
func maxSlidingWindow(nums []int, k int) []int {
// 双端队列。
q := []int{}
push := func(i int) {
for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
q = q[:len(q)-1]
}
q = append(q, i)
}
// 初始化第一个窗口对应的队列。
for i := 0; i < k; i++ {
push(i)
}
n := len(nums)
r := make([]int, 1, n-k+1)
r[0] = nums[q[0]]
// 移动窗口。
for i := k; i < n; i++ {
push(i)
// 如果队列首部元素下标不在窗口则移除。
if q[0] <= i-k {
q = q[1:]
}
r = append(r, nums[q[0]])
}
return r
}
参考文献
239. 滑动窗口最大值
