Poison

239. Sliding Window Maximum

Priority Queue
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
class Solution {
private static class Element {
private final int value;
private final int index;

public Element(int value, int index) {
this.value = value;
this.index = index;
}
}

public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
return new int[0];
}

int[] res = new int[nums.length - k + 1];

Queue<Element> maxHeap = new PriorityQueue<>((o1, o2) -> o2.value - o1.value);
for (int i = 0; i < k - 1; i++) {
maxHeap.offer(new Element(nums[i], i));
}

for (int j = k - 1; j < nums.length; j++) {
maxHeap.offer(new Element(nums[j], j));
int i = j - k + 1; // window: [i, j]
int evictedIndex = i - 1;

while (maxHeap.peek().index <= evictedIndex) {
maxHeap.poll();
}
res[j - k + 1] = maxHeap.peek().value;
}

return res;
}
}
Monotonic Queue
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
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];

// 非严格单调递增队列,允许包含重复值,first -> ... -> last
Deque<Integer> increaseDeque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
while (!increaseDeque.isEmpty() && num > increaseDeque.getFirst()) {
// 当前 num 比队首元素大,则队首元素可以安全移除,因为更大的元素出现了
increaseDeque.removeFirst();
}
increaseDeque.addFirst(num); // 将当前元素添加至队首

int evictedIndex = i - k;
if (evictedIndex >= 0 && increaseDeque.getLast() == nums[evictedIndex]) {
increaseDeque.removeLast();
}

if (i >= k - 1) {
// 此时可以收集最大值
res[i - k + 1] = increaseDeque.getLast();
}
}

return res;
}
}
Reference

239. Sliding Window Maximum
剑指 Offer 59 - I. 滑动窗口的最大值