[stack and queue topics] - sliding window

deque

1. The concept of double ended queue ：
Ordinary queues can delete elements at the head of the queue , Add elements at the end of the team . For double ended queues , At the head of the team 、 The tail of the team can enter and leave the team .

• Out of line and in line at one end , It's kind of like a stack , After the first out
• There are also restricted double ended queues ：
  You can join the team at one end 、 Out of line operation , The other end can only join the team ;
  You can join the team at one end 、 Out of line operation , The other end can only be out of line .

2. Basic operation of double ended queue ：

queue.peek() == queue.peekFirst() Check out the team leader element
queue.peekLast() Check out the end of the team elements
queue.add() == queue.addFirst() Add elements from the head of the team
queue.addLast() Add elements from the end of the team
queue.poll() == queue.pollFirst() Delete team leader element
queue.pollLast() Delete end of team element

LeetCode 239: Maximum sliding window

️ Their thinking ：

（1） Create a result set array , The size is nums.length - k + 1

（2） Create a double ended queue , Save the index of the elements put in the queue .

If the queue is empty , Then directly put the element index into the queue ; If the queue is not empty , And the new element is larger than the previous element , Then pop up the last element , Then join the current element into the team
because At present The maximum value in the window must not be smaller than the current element to be entered

（3） Determine whether the current maximum value is still in the sliding window , If it's no longer in the window , To pop the index of this element from the head of the queue

（4） Save the maximum value in the window to the result set array

️ Code section ：

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

        // Special case handling 
        if(nums == null || nums.length < 2){
    
            return nums;
        }
        // Result set array 
        int [] res = new int [nums.length - k + 1];
        // Use a double ended queue to save the array index 
        LinkedList<Integer> queue = new LinkedList();

        // Traversal array 
        for(int i = 0; i < nums.length; i++){
    
            // If the queue is not empty , The current in-line element is smaller than the next queued element , Then pop up the elements in the team 
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
    
                queue.pollLast();
            }

            // Queue the index of the current element 
            queue.addLast(i);

            // Determine whether the value in the queue is valid 
            if(queue.peek() <= i - k){
    
                queue.poll();
            }

            // Saves the maximum value in the slider to the result set , Mainly control the first input element 
            if(i + 1 >= k){
    
                res[i - k + 1] = nums[queue.peek()];
            }
        }
        return res;
    }
}