LeetCode - Sliding Window Maximum
Problem description
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Follow up:
- Could you solve it in linear time?
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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
Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
Analysis
The first thought is to use a maximum heap to do this. But TLE with TC O(Nlogk).
And then the idea is to use Deque. And for each step, we remove the item in the deque which has a smaller value than current item. And form the Deque to be a descending 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
// TLE
// public int[] maxSlidingWindow(int[] nums, int k) {
// int[] res = new int[nums.length -k + 1];
// PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2)->{return o2-o1;});
// for (int i = 0; i < k - 1; i++){
// pq.offer(nums[i]);
// }
// for (int i = 0; i < nums.length -k +1; i++){
// pq.offer(nums[i+k-1]);
// res[i] = pq.peek();
// pq.remove(nums[i]);
// }
// return res;
// }
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
// init deque and output
this.nums = nums;
int max_idx = 0;
for (int i = 0; i < k; i++) {
clean_deque(i, k);
deq.addLast(i);
// compute max in nums[:k]
if (nums[i] > nums[max_idx]) max_idx = i;
}
int [] output = new int[n - k + 1];
output[0] = nums[max_idx];
// build output
for (int i = k; i < n; i++) {
clean_deque(i, k);
deq.addLast(i);
output[i - k + 1] = nums[deq.getFirst()];
}
return output;
}
ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
int [] nums;
public void clean_deque(int i, int k) {
// remove indexes of elements not from sliding window
if (!deq.isEmpty() && deq.getFirst() == i - k)
deq.removeFirst();
// remove from deq indexes of all elements
// which are smaller than current element nums[i]
while (!deq.isEmpty() && nums[i] > nums[deq.getLast()])
deq.removeLast();
}
}