[LintCode] Sliding Window Maximum

Problem:

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Thinking:

维护一个deque来保存index，保证：
（1）从 deque.peekLast() 到 deque.peekFirst() 对应的nums[i] (deque.peekFirst() <= i <= deque.peekLast()) 的值递减
（2）对于第i个滑动窗口，deque.peekLast() > i - k，即deque的最后一个元素一定在当前的第 i 个滑动窗口内。
（3）对于第i个滑动窗口，对应的maximum值一定是 deque.peekLast()。

Java Code:

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        Deque<Integer> deque = new LinkedList<Integer>();
        deque.add(0);
        
        for (int i = 1; i < k; i++) {
            while (deque.size() > 0 && nums[i] >= nums[deque.peekFirst()]) {
                deque.pollFirst();
            }
            deque.addFirst(i);
        }
        
        for (int i = k; i < nums.length; i++) {
            result.add(nums[deque.peekLast()]);
            
            while (deque.size() > 0 && nums[i] > nums[deque.peekFirst()]) {
                deque.removeFirst();
            }
            deque.addFirst(i);
            
            if (deque.peekLast() <= i - k) {
                deque.removeLast();
            }
        }
        
        result.add(nums[deque.peekLast()]);
        return result;
    }
}

优化了一下（2015-07-19）（这个是 LeetCode 的了）：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int[] result = new int[nums.length - k + 1];
        
        Deque<Integer> deque = new LinkedList<Integer>();
        
        for (int i = 0, j = 0; j < result.length; i++) {
            while (deque.size() != 0 &&
                   nums[deque.peekFirst()] < nums[i]) {
                deque.removeFirst();
            }
            deque.addFirst(i);
            
            if (i < k - 1) {
                continue;
            }
            
            if (deque.peekLast() <= i - k) {
                deque.removeLast();
            }
            result[j++] = nums[deque.peekLast()];
        }
        
        return result;
    }
}

Reference:

http://codercareer.blogspot.com/2012/02/no-33-maximums-in-sliding-windows.html