Leetcode-239-Sliding Window Maximum

Sliding Window Maximum

leetcode: https://leetcode.com/problems/sliding-window-maximum/

Description:

You are given an array of integers 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.

Return the max sliding window.

Idea:

**solution **

Step1: Set the Deque to record the maximum of each window, and create array to store them.

Step2: traverse the nums array

Step3: if the current element>=the last element of the queue, remove the last element(the queue will have new tail), until the queue is empty or the current element< the new tail of the queue. If the current element < the last element of the queue, add it to the tail.

Step4: Because add the smaller element to the tail, so the first element of the queue is biggest.

Step5: if the right bound larger than the window, return the first element of queue to the array(record the index of it).

Step6: If the index of first element < the left bound of window, it means it isn’t in the window, then remove it.

Code:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //create the array to record the maximum of each window
        //n-k+1 is the nummber of windows in the nums array
        int[] result = new int[nums.length-k+1];
        
        //create the deque to record the compare the elements in the window
        LinkedList<Integer> deque = new LinkedList<>();
        //set left bound of the window
        int left = 0;
        //set the right bound of the window
        for(int right=0; right<nums.length; right++){
            
            //get the current element, when it larger than the tail element, remove tail until it < tail
            //because the stack stores the index of element, so we need compare the nums[i], nums[index]
            while(!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]){
                deque.removeLast();
            }
            
            //if current element < tail element, add them to the tail
            deque.addLast(right);
            
            //it means the right index move to the right bound of the window
            if(right>=k-1){
                //if the first element's index < left bound, it means it isn't in the window, remove the element
                if(deque.peekFirst()<left){
                    deque.removeFirst();
                }
                 //because add the element to the tail,so the first element in the stack is the maximum
                result[left++] = nums[deque.getFirst()];
            }
        }
        return result;
    }
}