Sliding Window Maximum
LeetCode https://leetcode.cn/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
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < 1 || k < 0 || k > nums.length) {
return nums;
}
int[] res = new int[nums.length - k + 1];
int resIndex = 0;
Deque<Integer> deque = new ArrayDeque<>(k);
int start = 0;
for (int end = 0; end < nums.length; end++) {
while (!deque.isEmpty() && nums[end] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(end);
if (end - start + 1 == k) {
res[resIndex++] = nums[deque.peekFirst()];
if (deque.peekFirst() == start++) {
deque.pollFirst();
}
}
}
return res;
}
}
Complexity
- Time = O(n)
- Space = O(n)
This post is licensed under CC BY 4.0 by the author.