题目描述

给你一个整数数组 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 <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

解题思路

大根堆/优先队列

首先想到使用大根堆来维护滑动窗口的最大值。每次将新元素加入堆中，并移除不在窗口内的元素。这样可以保证每次获取堆顶元素就是当前窗口的最大值。

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
import "container/heap"

type IntHeap [][2]int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i][0] > h[j][0] || (h[i][0] == h[j][0] && h[i][1] < h[j][1])
}

func (h *IntHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *IntHeap) Push(v interface{}) {
	*h = append(*h, v.([2]int))
}

func (h *IntHeap) Pop() interface{} {
	ans := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return ans
}

func maxSlidingWindow(nums []int, k int) []int {
	h := make(IntHeap, k-1, k)
	for i := 0; i < k-1; i++ {
		h[i] = [2]int{nums[i], i}
	}
	heap.Init(&h)

	ans := []int{}
	for i := k - 1; i < len(nums); i++ {
		heap.Push(&h, [2]int{nums[i], i})
		for h.Len() > 0 && h[0][1] <= i-k {
			heap.Pop(&h)
		}
		ans = append(ans, h[0][0])
	}

	return ans
}

这样写能通过所有测试用例，但时间复杂度是 O(n log k)，其中 n 是数组的长度，k 是滑动窗口的大小。

双端队列 / 单调队列

考虑使用双端队列来优化，核心思想是用一个类似 Redis 的 List 的双端队列来存储滑动窗口内的元素索引。在队列中越后面的元素索引越大，越前面的元素索引越小。这样可以保证队列的头部始终是当前窗口的头部元素索引如果在滑动窗口内则队列中的所有元素都在当前窗口内。队列中元素索引在数组（nums）中对应的值是单调递减的，也就是队头元素是当前窗口的最大值，而队尾元素是当前窗口的最小值。

这样每次只需要移除不在窗口内的元素，同时移除队中比当前元素小的元素，然后将新元素加入队列，就可以保证队列的头部始终是当前窗口的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSlidingWindow(nums []int, k int) []int {
	ans := make([]int, 0, len(nums)-k+1)
	for i, deque := 0, make([]int, 0, k); i < len(nums); i++ {
		for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)
		if x := i - k + 1; x >= 0 {
			for deque[0] < x {
				deque = deque[1:]
			}
			ans = append(ans, nums[deque[0]])
		}
	}

	return ans
}

这样写的时间复杂度是 O(n)，其中 n 是数组的长度，因为每个元素最多被添加和删除一次。