题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
- 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
- 输出：[3,3,5,5,6,7]
解释：
1
2
3
4
5
6
7
8
|
滑动窗口的位置 最大值
--------------- -----
[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
|
var a []int
type PriorityQueue struct {
sort.IntSlice
}
func (pq *PriorityQueue) Less(i, j int) bool {
// 注意：优先队列里存储的是下标，所以比较时要取下标对应的元素
return a[pq.IntSlice[i]] > a[pq.IntSlice[j]]
}
func (pq *PriorityQueue) Push(v interface{}) {
pq.IntSlice = append(pq.IntSlice, v.(int))
}
func (pq *PriorityQueue) Pop() interface{} {
tmp := pq.IntSlice
v := tmp[len(tmp)-1]
pq.IntSlice = tmp[:len(tmp)-1]
return v
}
func maxSlidingWindow(nums []int, k int) []int {
a = nums
pq := &PriorityQueue{make([]int, k)}
for i := 0; i < k; i++ {
pq.IntSlice[i] = i
}
heap.Init(pq)
n := len(nums)
ans := make([]int, n-k+1)
ans[0] = a[pq.IntSlice[0]]
for i := k; i < n; i++ {
heap.Push(pq, i)
for pq.IntSlice[0] <= i-k {
heap.Pop(pq)
}
ans[i-k+1] = a[pq.IntSlice[0]]
}
return ans
}
|
解法二：单调双端队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func maxSlidingWindow(nums []int, k int) []int {
deque := make([]int, k)
push := func(i int) {
for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
for i := 0; i < k; i++ {
push(i)
}
ans := make([]int, len(nums)-k+1)
ans[0] = nums[deque[0]]
for i := k; i < len(nums); i++ {
push(i)
for deque[0] <= i-k {
deque = deque[1:]
}
ans[i-k+1] = nums[deque[0]]
}
return ans
}
|
