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 sizek = 3. return[7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8], return the maximum7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum8;

Solution:

hashheap: O(nlogk)

deque: O(n)

用单调递减deque

每次加入新元素到deque尾时，先把它前面比它小的数都弹出，因为它们不会再是max，没有用，所以维护了递减的序列；i >= k后，要把deque头的旧max弹出，当deque头 == array[i - k]时，弹出。

  public List<Integer> maxWindows(int[] array, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {
      inqueue(deque, array[i]);
      if (i + 1 < k) {
        continue;
      }
      if (i >= k) {
        remove(deque, array[i - k]);
      }
      ans.add(deque.peekFirst());
    }
    return ans;
  }
  private void inqueue(Deque<Integer> deque, int num) {
    while (!deque.isEmpty() && deque.peekLast() < num) {
      deque.pollLast();
    }
    deque.offerLast(num);
  }
  private void remove(Deque<Integer> deque, int num) {
    if (!deque.isEmpty() && deque.peekFirst() == num) {
      deque.pollFirst();
    }
  }