Maximum Number within Window

Medium

Given an integer array A and a sliding window of size K, find the maximum value of each window as it slides from left to right.

Assumptions

• The given array is not null and is not empty

• K >= 1, K <= A.length

Examples

A = {1, 2, 3, 2, 4, 2, 1}, K = 3, the windows are {{1,2,3}, {2,3,2}, {3,2,4}, {2,4,2}, {4,2,1}},

and the maximum values of each K-sized sliding window are [3, 3, 4, 4, 4]

Solution: Descending deque to maintain greatest number in current window

top of the deque will always be the greatest

it can be replaced in two ways:

1. it is outside of the window. PollFirst()

2. A greater number has been discovered. PollLast()

When new number enters. He must first remove all elements lesser than him, because he will be dominant until he exits the queue.

public class Solution {
  public List<Integer> maxWindows(int[] array, int k) {
    List<Integer> result = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>();
    //Rule of deque
    //new indexes come from below
    //when new int coming in is greater than prev: remove prev smaller ones.
    //when index is out of window, remove from top
    for(int i = 0; i <array.length; i++){
      while(!deque.isEmpty() && array[i] >= array[deque.peekLast()]){
        deque.pollLast();
      }

      if(!deque.isEmpty() && deque.peekFirst() <= i - k){
        deque.pollFirst();
      }

      deque.offerLast(i);
      if (i >= k - 1) result.add(array[deque.peekFirst()]);
    }
    return result;

  }
}

TC: O(N) Every index goes in to the queue only once

SC: O(K) k elements in queue at max. ex: k = 3, Front { 9, 8 ,7 } Back