Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
Example
For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]
At first the window is at the start of the array like this
We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.
At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1),i] or any subsequent window. This means
If an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array
Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the "max" in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.
As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]
public class Solution {
// Make sure the maximum number is at the head of the deque
public void inQueue(Deque<Integer> deque, int num) {
while (!deque.isEmpty() && deque.peekLast() < num) {
deque.pollLast();
}
deque.offerLast(num);
}
// Remove the previous numbers for sliding window constraints
public void outQueue(Deque<Integer> deque, int num) {
if (deque.peekFist() == num) {
deque.pollFist();
}
}
/**
* @param nums: A list of integers.
* @return: The maximum number inside the window at each moving.
*/
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> ans = new ArrayList<Integer>();
Deque<Integer> deque = new ArrayDeque<Integer>();
if (nums == null || nums.length == 0) {
return ans;
}
// Initialize the deque with first k - 1 element
for (int i = 0; i < k - 1; i++) {
inQueue(deque, nums[i]);
}
// Continue from k-th element, for the maximum in each sliding window
for (int i = k - 1; i < nums.length; i++) {
inQueue(deque, nums[i]);
ans.add(deque.peekFirst());
outQueue(deque, nums[i - k + 1]);
}
}
}
*Deque - Storing Index in Deque - Monotonic Queue (17ms 51.07% AC)
The dq head always stores the index of maximum in the sliding window
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || n == 1 || k == 1) {
return nums;
}
int[] result = new int[n - k + 1];
// Store index
LinkedList<Integer> dq = new LinkedList<>();
for (int i = 0; i < n; i++) {
// remove index out of sliding window [i - k + 1, i]
if (!dq.isEmpty() && dq.peek() < i - k + 1) {
dq.poll();
}
// remove numbers in deque which are smaller than the new element nums[i] in the sliding window
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offer(i);
if (i - k + 1 >= 0) {
result[i - k + 1] = nums[dq.peek()];
}
}
return result;
}
}
Alternative Approach 1 - Time O(n) Space O(1) (1ms AC)
max_index - the index of maximum in current (or previous if in next loop) sliding window
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int size = nums.length;
if( nums.length == 0 || k == 0 || k > nums.length)
return new int[0];
int[] max_window = new int[size-k+1];
int max =0;
int max_index =-1;
int index=0;
for(int j =0;j<size-k+1;j++)
{
if(j>max_index)
{
max_index = j;
for(int m =j;m<j+k;++m)
{
if(nums[m]>= nums[max_index])
max_index=m;
}
}
else
{
if(nums[j+k-1] > nums[max_index])
max_index= j+k-1;
}
max_window[index++] = nums[max_index];
}
return max_window;
}
}
Alternative Approach 2 - Two max arrays - Time O(n) Space O(n) - (4ms AC)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || nums.length == 1)
return nums;
int[] max_left = new int[nums.length]; // max from the left
int[] max_right = new int[nums.length]; // max from the right
int n = nums.length;
// initialize starting points for left and right
max_left[0] = nums[0]; // max for first value from the left is just first val in nums
max_right[n - 1] = nums[n - 1]; // max for last value is last val since we start here
// partition array into windows of size k
for (int i = 1; i < n; i++)
{
// see if this is the first number in the partition, if so then the max is
// the value at that index in nums, otherwise you get max between the previous
// max value and current value in nums
// go through each number in the partition and update the max for the numbers
// up to that index in the partition, in the end the last number in partition
// will have the max for this partition
max_left[i] = (i % k) == 0 ? nums[i] : Math.max(max_left[i - 1], nums[i]);
// get index for right side
int j = n - i - 1;
// do the same thing as max_left, but for the right side so we are going
// from right to left
max_right[j] = (j % k == 0) ? nums[j] : Math.max(max_right[j + 1], nums[j]);
}
// there are n - k + 1 sliding windows, since we start from 0, 1, 2,...until n - k
// so going from index 0 to n-k, total is n - k + 1 windows
int[] sliding_max = new int[n - k + 1];
for (int i = 0; i < sliding_max.length; i++)
{
// max is either value at index i in max_right, or the last value in this
// sliding window for max_left, since we went from left to right for that
// so max is the last one in the sliding window
sliding_max[i] = Math.max(max_right[i], max_left[i + k - 1]);
}
return sliding_max;
}
}