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

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

then the window move one step forward.

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

then the window move one step forward again.

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

Challenge
o(n) time and O(k) memory

Hash Heap

这个题目可以用Heap做，写起来很简单，就是删除的时候时间复杂度过高，会超时，要自己实现Hash Heap.

Deque

这种做法是，在deque中只保留可能为答案的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> ans = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        while (!deque.isEmpty() && num > deque.peekLast()) {
            deque.pollLast();
        }
        deque.add(num);
        if (i > k - 1 && deque.peekFirst() == nums[i - k])
            deque.pollFirst();
        if (i >= k - 1) {
            ans.add(deque.peek());
        }
    }
    return ans;
}