239. Sliding Window Maximum (Hard)

Given an array nums, there is a sliding window of size k which 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.

For example,
Given nums=[1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as[3,3,5,5,6,7].

Note:
You may assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:

Could you solve it in linear time?
Hint: （地方换了）

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

题意：返回每个滑动窗口的最大值，总数是nums.length - k + 1。

Solution 1: maxHeap O(k * n); O(k)

用maxHeap模拟滑动窗口，存的是value，不是index。

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        if (nums.length == 0) return new int[0];
        Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);//最大堆

        for (int i = 0; i < k; i++) {
            maxHeap.add(nums[i]); //queue的大小是k，不是n
        }
        res[0] = maxHeap.peek(); //必须先这么写，否则会越界。反例代码见下
        for (int i = 1; i <= n - k; i++) {
            maxHeap.remove(nums[i - 1]); //heap的remove操作是O(k)复杂度！
            maxHeap.add(nums[i - 1 + k]);
            res[i] = maxHeap.peek();
        }
//        for (int i = 0; i <= n - k; i++) {
//            res[i] = maxHeap.peek();
//            maxHeap.remove(nums[i]);
//            maxHeap.add(nums[i + k]);
//        }
        return res;
    }

Solution 2: Deque O(n); O(k)

用Deque模拟滑动窗口，Deque存的是index，不是value，index从大到小排序。

    // 注意是往deque里加array的index，使得deque中存的index对应的数组value单调递减
    //（deque中的index即为window可能的max值的index）
    // 比如原题例子中Deque先存入0，然后nums[1]>nums[0]，就要把Deque中的最后一个元素0删除
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k < 1 || k > nums.length) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        // 这个新建的deque相当于一个单调递减的deque（PQ?）
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 如果deque中第一个值不在窗口范围中了，remove之；i-k+1是window的左边界
            while (!deque.isEmpty() && deque.peekFirst() == i - k) { //i>=k的时候才开始删
                deque.removeFirst();
            }
            // 如果新的值大于deque尾部的一些值，删除它们（它们比新加的值还小，就不可能变成max了，类似于pruning）
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            if (i + 1 - k >= 0) {
                res[i + 1 - k ] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums, 3)));
    }

Follow up:
Could you solve it in linear time?

面经：就是给你一串数list，然后window size k，从第一个数开始去往后slide这个window，算每次slide之后的minimum，返回一个list