题目描述
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
- 输入: 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
提示：
你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。
注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/
解法一：优先队列
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
|
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(x any) {
pq.IntSlice = append(pq.IntSlice, x.(int))
}
func (pq *priorityQueue) Pop() any {
ret := pq.IntSlice[len(pq.IntSlice)-1]
pq.IntSlice = pq.IntSlice[:len(pq.IntSlice)-1]
return ret
}
func maxSlidingWindow(nums []int, k int) []int {
a = nums
n := len(nums)
pq := &priorityQueue{make([]int, k)}
for i := 0; i < k; i++ {
pq.IntSlice[i] = i
}
heap.Init(pq)
ans := make([]int, 1, n-k+1)
ans[0] = nums[pq.IntSlice[0]]
for i := k; i < n; i++ {
heap.Push(pq, i)
for len(pq.IntSlice) > 0 && pq.IntSlice[0] <= i - k {
heap.Pop(pq)
}
ans = append(ans, nums[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
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
type (
Deque struct {
first *node
last *node
size int
}
node struct {
prev *node
item interface{}
next *node
}
)
func NewDeque() *Deque {
return &Deque{}
}
func (q *Deque) linkFirst(val interface{}) {
f := q.first
newNode := &node{nil, val, q.first}
q.first = newNode
if nil == f {
q.last = newNode
} else {
f.prev = newNode
}
q.size++
}
func (q *Deque) unlinkFirst(f *node) interface{} {
// assert f == first && f != nil
val := f.item
next := f.next
f.item = nil
f.next = nil
q.first = next
if nil == next {
q.last = nil
} else {
next.prev = nil
}
q.size--
return val
}
func (q *Deque) linkLast(val interface{}) {
l := q.last
newNode := &node{l, val, nil}
q.last = newNode
if nil == l {
q.first = newNode
} else {
l.next = newNode
}
q.size++
}
func (q *Deque) unlinkLast(l *node) interface{} {
// assert l == last && l != nil
val := l.item
prev := l.prev
l.item = nil
l.prev = nil
q.last = prev
if nil == prev {
q.first = nil
} else {
prev.next = nil
}
q.size--
return val
}
func (q *Deque) Len() int {
return q.size
}
func (q *Deque) IsEmpty() bool {
return q.Len() == 0
}
func (q *Deque) PushFront(val interface{}) {
q.linkFirst(val)
}
func (q *Deque) PushBack(val interface{}) {
q.linkLast(val)
}
func (q *Deque) PeekFront() interface{} {
if nil == q.first {
return nil
}
return q.first.item
}
func (q *Deque) PeekBack() interface{} {
if nil == q.last {
return nil
}
return q.last.item
}
func (q *Deque) PopFront() interface{} {
if nil == q.first {
panic("deque is empty")
}
return q.unlinkFirst(q.first)
}
func (q *Deque) PopBack() interface{} {
if nil == q.last {
panic("deque is empty")
}
return q.unlinkLast(q.last)
}
func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
ans := make([]int, n-k+1)
deque := NewDeque()
for i := 0; i < k; i++ {
for !deque.IsEmpty() && deque.PeekBack().(int) < nums[i] {
deque.PopBack()
}
deque.PushBack(nums[i])
}
ans[0] = deque.PeekFront().(int)
for i := k; i < n; i++ {
if deque.PeekFront().(int) == nums[i-k] {
deque.PopFront()
}
for !deque.IsEmpty() && deque.PeekBack().(int) < nums[i] {
deque.PopBack()
}
deque.PushBack(nums[i])
ans[i-k+1] = deque.PeekFront().(int)
}
return ans
}
|
