239. 滑动窗口最大值
hard 队列
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
| 输入：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
|
单调队列
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。也就是维护一个从队头到队尾递减的单调队列
设计单调队列的时候，pop，和 push 操作要保持如下规则：
- pop(value)：如果窗口移除的元素 value 等于单调队列的头元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果 push 的元素 value 大于尾元素的数值，那么就将队列尾元素弹出，直到 push 元素的数值小于等于队列尾元素的数值为止
保持如上规则，每次窗口移动的时候，只要问 que.front() 头元素就可以返回当前窗口的最大值。
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
45
46
47
| type queue struct {
Q []int
}
func (q *queue) back() int {
return q.Q[len(q.Q)-1]
}
func (q *queue) front() int {
return q.Q[0]
}
func (q *queue) len() int {
return len(q.Q)
}
func (q *queue) push(num int) {
for q.len() != 0 && num > q.back() {
q.Q = q.Q[:q.len()-1]
}
q.Q = append(q.Q, num)
}
func (q *queue) pop(num int) {
if q.len() != 0 && num == q.front() {
q.Q = q.Q[1:]
}
}
func maxSlidingWindow(nums []int, k int) []int {
result := make([]int, 0)
q := &queue{Q: make([]int, 0)} // 从队头到队尾递减的单调队列
for i := 0; i < k; i++ {
q.push(nums[i])
}
result = append(result, q.front())
i, j := 1, k
for j < len(nums) {
q.pop(nums[i-1])
q.push(nums[j])
result = append(result, q.front())
i++
j++
}
return result
}
|
或者这样，将 queue 直接定义成 []int，不过要注意指针传递与值传递的区别
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
45
46
47
48
49
50
51
| // 从队头到队尾递减的单调队列
type queue []int
// 取队尾
func (q queue) back() int {
return q[len(q)-1]
}
// 取队头
func (q queue) front() int {
return q[0]
}
func (q queue) len() int {
return len(q)
}
func (q *queue) push(num int) {
for q.len() != 0 && num > q.back() {
// 一个个踢掉比num小的元素
*q = (*q)[:q.len()-1] // 必须用指针，否则会因为值传递而不能成功赋值，下同
}
*q = append(*q, num)
}
func (q *queue) pop(num int) {
if q.len() != 0 && num == q.front() {
// num等于队头时才弹出，否则num不会在队列中
*q = (*q)[1:]
}
}
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
q := queue(make([]int, 0))
// 放置滑动窗口初始位置
for i := 0; i < k; i++ {
q.push(nums[i])
}
res = append(res, q.front())
i, j := 1, k
for j < len(nums) {
q.pop(nums[i-1])
q.push(nums[j])
res = append(res, q.front())
i++
j++
}
return res
}
|
