[sword finger offer] 59 - I. maximum value of sliding window

The finger of the sword Offer 59 - I. Maximum sliding window

subject

Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows .

Ideas

• Traverse the elements in a given array , If the queue is not empty and the currently inspected element is greater than or equal to the end of the queue element , Then remove the tail element , Until the queue is empty or the current review element is smaller than the new tail element
• When the subscript of the first element is smaller than the left boundary of the sliding window Left Indicates that the team leader element no longer belongs to the sliding window , Remove it from the team head element
• Because array subscript from 0 Start , So when the right edge of the window right + 1>= k, It means that the window has been formed . At this time, the first element of the queue is the maximum value in the window .

Code

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    

        if(nums.length == 0)
        {
    
            return new int[0];
        }
        
        //  Number of windows 
        int[] res = new int[nums.length - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();

        //  Traverse the elements in the array , right Represents the right boundary of the sliding window 
        for(int right = 0; right < nums.length; right++)
        {
    
            //  If the queue is not empty   And the current element is greater than or equal to the tail element   Remove the tail element 
            //  until   The queue is empty   Or the current element is smaller than the new tail element 
            while(!queue.isEmpty() && nums[right] >= nums[queue.peekLast()]){
    
                queue.removeLast();
            }

            //  Storage element subscript 
            queue.addLast(right);

            //  Calculate the left boundary of the window 
            int left = right - k + 1;
            

            // When the subscript of the first element is less than the left boundary of the sliding window Left
            //  Indicates that the team leader element is no longer sliding inside the window   Remove it from the head of the team 

            if(queue.peekFirst() < left)
            {
    
                queue.removeFirst();
            }

            //  From below 0 Start   So when right + 1 >= k  It indicates that the sliding window has been formed   The first element of the queue is the maximum value of the window 
            if(right + 1 >= k)
            {
    
                res[left] = nums[queue.peekFirst()];//  Store the team leader element in res in 
            }

        }
        return res;
    }
}