239. Sliding Window Maximum

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example, Givennums=[1,3,-1,-3,5,3,6,7], andk= 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?

Thoughts:

1. O(nlogk): Maintain a max heap of k elements

2. O(n): Have a deque to keep track of current window maximum

Code: Heap

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        if(nums.length == 0) return new int[0];
        Queue<Integer> queue = new PriorityQueue<Integer>((n1, n2) -> n2 - n1);

        int i = 0;
        for(; i < k; i ++) queue.add(nums[i]);

        result[i - k] = queue.peek();

        for(; i < len; i ++){
            queue.remove(nums[i - k]);
            queue.add(nums[i]);
            result[i - k + 1] = queue.peek();
        }

        return result;
    }
}

Code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty() || k <= 0) return nums;
        int n = nums.size();
        vector<int> windowMax; 
        deque<int> dq;
        for(int i = 0; i < nums.size(); i ++){
            // check in the range
            while(!dq.empty() && dq.front() < i - k  + 1){
                dq.pop_front();
            }
            // remove smaller numbers in k range as they are useless
            while(!dq.empty()&& nums[dq.back()] < nums[i]){
                dq.pop_back();
            }
        dq.push_back(i);
        if(i >= k - 1){ windowMax.push_back(nums[dq.front()]);}
        }
     return windowMax;
    }

};

Python

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d += i,
            if d[0] == i - k:
                d.popleft()
            if i >= k - 1:
                out += nums[d[0]],
        return out

Special Thanks to flyingpenguin and jianchaolifighter for the reference