-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_239.java
More file actions
26 lines (23 loc) · 713 Bytes
/
Copy pathP_239.java
File metadata and controls
26 lines (23 loc) · 713 Bytes
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
package leetcode.hard;
import java.util.ArrayDeque;
import java.util.Deque;
public class P_239 {
public int[] maxSlidingWindow(int[] nums, int k) {
final Deque<Integer> dq = new ArrayDeque<>();
final int n = nums.length;
final int[] res = new int[n - k + 1];
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.getFirst() == i - k) {
dq.removeFirst();
}
while (!dq.isEmpty() && nums[i] > nums[dq.getLast()]) {
dq.removeLast();
}
dq.addLast(i);
if (i + 1 >= k) {
res[i - k + 1] = nums[dq.getFirst()];
}
}
return res;
}
}