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
38
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) {
int[] array = new int[nums.length - k + 1];

Queue<Element> priorityQueue = new PriorityQueue<>((a, b) -> b.value - a.value); // 注意使用大根堆
for (int i = 0; i < k; i++) {
priorityQueue.add(new Element(nums[i], i));
}

array[0] = priorityQueue.peek().value;

for (int j = k; j < nums.length; j++) {
// 注意需要先添加元素,再移除元素,避免窗口为空导致 NPE, 如 [1, -1], k = 1 时
// 如果后添加元素,则需要在 while 中对队列进行空判断,不能直接调用 peek 方法
priorityQueue.add(new Element(nums[j], j));

// 这段逻辑非常关键,保证了堆顶的元素一定在窗口内,即最大值一定是当前窗口内的元素,便于后续进行收集
// 注意此处需要使用 while, 可以结合数组 [9, 10, 9, -7, -4, -8, 2, -6], k = 5 加深理解,防止最后一个窗口使用下标为 0 的 9 作为最大值
while (priorityQueue.peek().index <= j - k) {
priorityQueue.poll();
}

array[j - k + 1] = priorityQueue.peek().value;
}

return array;
}
}
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[] ans = new int[nums.length - k + 1];

Deque<Integer> deque = new LinkedList<>(); // 队列元素从左至右递减
for (int j = 0; j < nums.length; j++) {
int i = j - k + 1; // window: [i, j]

// 注意 nums[i - 1] 才是被移除的元素
if (i > 0 && !deque.isEmpty() && deque.getFirst() == nums[i - 1]) {
// 队列最大值已处于窗口左侧则移除
deque.removeFirst();
}
while (!deque.isEmpty() && deque.getLast() < nums[j]) {
// 保持队列单调递减
deque.removeLast();
}

deque.add(nums[j]);

if (i >= 0) {
ans[i] = deque.getFirst();
}
}

return ans;
}
}
Reference

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