Sliding Window Maximum

Sliding Window Maximum

23%

Accepted

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.

Have you met this question in a real interview? 

Yes

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

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>();

        Deque<Integer> deque = new LinkedList<Integer>();

        if(nums == null || nums.length == 0 || k <= 0) return res;

        

        for(int i = 0; i < k; i++){

            

            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){

                deque.removeLast();

            }

            deque.addLast(i);

        }

        

        for(int i = k; i < nums.length; i++){

            res.add(nums[deque.peekFirst()]);

            while(!deque.isEmpty() && deque.peek() <= i - k){

                deque.removeFirst();

            }

            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){

                deque.removeLast();

            }

            deque.addLast(i);

        }

        res.add(nums[deque.peekFirst()]);

        return res;

    }

}