239 Sliding Window Maximum

ref: 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 thek 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 assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

分析

之前准备Pocket Gems的时候准备过的，这次做其实顺利的

要点：

• 用一个PriorityQueue每次能够自动peek到目前的最大的数

• 用一个map保存<index, nums[index]>，不可以反过来，不然重复的数字会丢失。

public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Map<Integer, Integer> map = new HashMap<>();
        int firstMax = nums[0];
        for(int i = 0; i < k; i++) {
            firstMax = Math.max(firstMax, nums[i]);
            pq.offer(nums[i]);
            map.put(i, nums[i]);
        }
        int len = nums.length;
        int[] res = new int[len - k + 1];
        res[0] = firstMax;
        for(int i = k; i < len; i++) {
            pq.offer(nums[i]);
            map.put(i, nums[i]);
            pq.remove(map.get(i - k));
            map.remove(i - k);
            res[i - k + 1] = pq.peek();
        }
        return res;
    }

我觉得有点精分的是，题目强调了k是valid，是大于零并且小于一个非空数组的长度，但是input array的长度可能是0，感觉挺无聊的= =

时间复杂度是O(n), 我认为准确说是O(n logk),因为每次给pq递一个数的时候是logk的复杂度，但是k supposed to be不大（和数组长度比起来），所以不是很重要