239. Sliding Window Maximum

原题链接：Sliding Window Maximum

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. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
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
Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?

Again 先上暴力解法。双层嵌套的循环，时间复杂度是O(N*k)=O(N)

class Solution {
    /**
     * Brute force: every time traverse the whole window to find the maximum. Time complexity: O(N*k)
     **/
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length < k) {
            return new int[0];
        }
        
        int[] maxs = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            int tempMax = Integer.MIN_VALUE;
            for (int j =  0; j < k; j++) {
                tempMax = Math.max(tempMax, nums[i + j]);
            }
            maxs[i] = tempMax;
        }
        
        return maxs;
    }
}

我一开始没有想到要使用别的数据结构。但是这道题的tag里还有Heap，我第一时间想到的是PriorityQueue。但发现优先队列并不好用因为每次对其进行改动之后就要再去查询一下min & max。看了一下网上比较通用的做法是维护一个单调递减的队列，用于存储备胎可能成为max of the window的数字的index。

从网上找了一个看起来非常简化的做法（感觉目前自己还没有办法独立写出这样的解法）。

class Solution {
    /**
     * [3,1,-1,-3,5,3,6,7]
     * deque={0,1}
     * i = 2. deque={0,1,2}, i + 1 == k -> maxs={3}
     * i = 3, deque={0,1,2,3}. deque.peek() = 0 < (i - k + 1). deque.pollFirst(). i + 1 > k => maxs={3, nums[1] = 1}
     * i = 4, !deque.isEmpty() == false. deque.addLast(i) => deque={4}. maxs={3,1,5}
     * i = 5, deque={4}, i - 4 + 1 < k. deque.addLast(i) => deque{4,5} => maxs={3,1,5,5}
     * i = 6, deque={4,5} => remove 4 and 5 => deque={6} => maxs={3,1,5,5,6}
     * i = 7, deque={6} => remove 6 => deque{7} => maxs={3,1,5,5,6,7}
     * Runtime: 11 ms, faster than 59.93% of Java online submissions for Sliding Window Maximum.
     * Memory Usage: 41.3 MB, less than 81.25% of Java online submissions for Sliding Window Maximum.
    **/
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length < k) {
            return new int[0];
        }
        
        int[] maxs = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            // 如果当前的数字比队列里之前的数字都要大，就把队列里这些不可能变成max的数字都移除
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }
            while (!deque.isEmpty() && i - deque.peekFirst() + 1 > k) {
                deque.pollFirst();
            }
            deque.addLast(i);
            
            // 由于是从头开始遍历，在检查到第k个元素之前是不会往results里写入的
            if (i + 1 >= k) {
                maxs[i + 1 - k] = nums[deque.peekFirst()];
            }
        }
        
        return maxs;
    }
}

More

• 了解Java Deque 的数据结构及其API特性。Java Document: Deque
• 在一篇讨论里有人提到了用红黑树这样的BST来存储备胎。虽然感觉并不必要不过既然提到了，也把红黑树这个数据结构放进bucket list吧。Wikipedia: 红黑树

Reference

单调队列
Blog: 初步了解红黑树
Java数据结构 Deque