Sliding Window Maximum 362

Question

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.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Solution

用Deque双端队列来解。分为添加元素和删除元素两部步。

1. 初始化第一个窗口（0-第k－1个元素），一次向deque中加入数组中的元素。每次加入新元素时，若deque中最后一个元素比新元素小，则删去，直到deque中最后一个元素比新元素大时停止（或deque为空时停止），然后加入新元素。

2. 添加元素：从第k的元素开始，每次加入新元素时，若deque中最后一个元素比新元素小，则删去，直到deque中最后一个元素比新元素大时停止（或deque为空时停止），然后加入新元素。此时deque中第一个元素即为当前窗口的最大值，加入答案中。

3. 删除元素：应该删去（当前位置－k）位置的元素，看deque第一个元素是否和要删除元素相等，若不相等则说明在之前的元素加入过程中该元素已经删去，则不用做任何操作，否则删去deque中第一个元素即可。

代码如下：

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> res = new ArrayList<Integer>();
        if(nums == null || nums.length < k || k <= 0){
            return res;
        }

        Deque<Integer> deque = new ArrayDeque<Integer>();
        for(int i = 0; i < k - 1; i++){
            while(!deque.isEmpty() && deque.getLast() < nums[i]){
                deque.removeLast();
            }
            deque.offer(nums[i]);
        }
        for(int i = k - 1; i < nums.length; i++){
            while(!deque.isEmpty() && deque.getLast() < nums[i]){
                deque.removeLast();
            }
            deque.offer(nums[i]);

            res.add(deque.getFirst());

            if(deque.getFirst() == nums[i - k + 1]){
                deque.removeFirst();
            }
        }

        return res;
    }
}