Leetcode 239. Sliding Window Maximum [Hard]

Not so hard for people familiar with streaming processing: You are given an array of integers nums, there is a sliding window of size kwhich 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.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Solution is based on using Deque where we keep only indeces of elements that are max in given window and remove everything smaller on each iteration. Intuitive implementation is:

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

int l = 0, r = k-1;
int[] ans = new int[nums.length-k+1];
Deque<Integer> dq = new LinkedList<>(); // keep indeces
// create 1st window
for(int i = l; i <= r; i++) {
// remove what is smaller than index r
while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
dq.offerLast(i);
}

ans[0] = nums[dq.peekFirst()];
l++; r++;
while(r<nums.length) {
// remove the left most element if available
while(!dq.isEmpty() && dq.peekFirst() < l) dq.pollFirst();
// remove what is smaller than index r
while(!dq.isEmpty() && nums[dq.peekLast()] < nums[r]) dq.pollLast();

dq.offerLast(r);

ans[l] = nums[dq.peekFirst()];
l++; r++;
}
return ans;
}
}

Each step can be visualized as: [l; r] -> [dequeue for this window]

[0;2]: [1, 2]
[1;3]: [1, 2, 3]
[2;4]: [4]
[3;5]: [4, 5]
[4;6]: [6]
[5;7]: [7]

Java, start-up, hiking, photos, bicycle,journey