239. Sliding window maximum

239. Maximum sliding window

Force link 239. Maximum sliding window

Give you an array of integers nums, There is a size of k The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see... In the sliding window k A digital . The sliding window moves only one bit to the right at a time .

Returns the maximum value in the sliding window .

Example 1：

Input ：nums = [1,3,-1,-3,5,3,6,7], k = 3
Output ：[3,3,5,5,6,7]
explain ：
Position of sliding window Maximum

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Their thinking ：

Violence law can solve .
Here, linear time complexity can be achieved by using double ended queues .

1、 Use queues to store larger elements . Team leader is the biggest element .
2、 If the element to be added is larger than the end of the queue , Take out the elements at the end of the team , Ensure that the queue is arranged in an increasing order .（ You only need to save larger values in the queue , Small values do not need to be saved ）
3、 If the element to be added is smaller than the end of the queue , Add directly to the end of the team .
4、 If the sliding window moves , The removed element is exactly equal to the team leader element , Remove the team leader element .

deque

deque Deque extends Queue, Elements can be inserted at both ends to get

offerFirst
offerLast

pollFirst
pollLast

peekFirst
peekLast

Realization

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
       // Keep larger elements in the queue , If there is a bigger , Cover 
       // If you remove the team leader , Delete .
       int[] result = new int[nums.length-k+1];
       int x = 0;
       if(nums==null || nums.length<=0){
           return result;
       }
       Deque<Integer> deque = new LinkedList<>();
       for(int i=0;i<nums.length;i++){
           if(!deque.isEmpty() && deque.peekLast()>nums[i]){
               deque.offerLast(nums[i]);
           }else{
          		// Be careful ： Ensure the order of the queue , When inserting elements , If the tail element is smaller than the newly inserted element , Delete the tail element , We need to continue to compare new tail elements .
               while(!deque.isEmpty() && deque.peekLast()<nums[i]){
                    deque.pollLast();
               }
                 deque.offerLast(nums[i]);
           }
           if(i>=k-1){
               result[x++]=deque.peekFirst();
               if(deque.peekFirst() == nums[i-k+1]){
                   deque.pollFirst();
               }
           }     
       }
       return result;
    }
}