Friday, September 4, 2015

Leetcode: 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.
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?
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.
Understand the problem:
If the problem is solved by using a heap, the complexity would be n logk. 
Since the problem asks for liner time solution, we can use a deque. 

We enqueue the element from the end of the deque, if the end of the deque is less than the current element, delete the current element. Then we enqueue the element into the end of the deque. If the size of the deque is greater than the k, we remove element from the front. 

Code (Java):
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        Deque<Integer> deque = new LinkedList<Integer>();
        int[] result = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            
            deque.addLast(i);
            
            // Remove if the size of the deque is greater than k
            if (i - deque.getFirst() + 1 > k) {
                deque.removeFirst();
            }
            
            // Add into the result
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[deque.getFirst()];
            }
        }
        
        return result;
    }
}

Summary:
Note that for a deque, first is the left end and Last is the right end. 
The numbers in the deque is actually in reversed sorted order (large first) from front to end.
[ 1 largest, 2nd largest, 3rd largest ...                                 ]
front                                                                                     end

1 comment:

  1. Hello, I love reading through your blog, I wanted to leave a little comment to support you and wish you a good continuation. Wish you best of luck for all your best efforts.. upvc windows | sliding doors windows

    ReplyDelete