题解 | #滑动窗口的最大值#

此问题的暴力解法，O(N*M),不能通过

O(N), O(N)

需要借助于双端队列进行操作，维护队列中元素为不严格单调递降，即单调队列

思路分析：打个比方，给定num = [1,3,3,2,1 ],size = 3,第一个窗口中，1,3,3 中最大值为3，然后滑动到第二个窗口，3,3,2最大值为3，我们只需要在队列中维护，窗口滑动过程中，最有可能成为最大值的可能，即不严格单调递降。因此，第一窗口时，队列中维护3,3，第二个窗口时，队列3,3,2，第三个窗口时，队列3,2,1，最大值都是队列的第一个

题外话，此题求窗口最大值，所以维护不严格单调递降，若是窗口最小值，维护队列为不严格单调递增即可

其中最为主要的两个操作，都是为了维护队列

1，维护队列中元素不严格单调递减

2，维护队列，让队列中的值，只含有此窗口中的元素，相当于判断队列中的头元素是否应该剔除，

import java.util.*;
public class Solution {//单调队列，队列中不严格递降
public ArrayList<Integer> maxInWindows(int [] num, int size) {
    ArrayList<Integer> res = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    for(int i = 0; i < size; i++){//先将前size个元素，加入队列
        while(!deque.isEmpty() && deque.peekLast() < num[i]){//更新队列，保证队列元素不严格递降，操作1
            deque.pollLast();
        }
        deque.add(num[i]);
    }
    
    res.add(deque.peekFirst());
    
    for(int i = size; i < num.length; i++){
        
        if(!deque.isEmpty() && deque.peekFirst() == num[i - size]){//更新队列，判断队列中的头元素是否应该剔除，操作2
            deque.pollFirst();
        }
        
        while(!deque.isEmpty() && deque.peekLast() < num[i]){//加入元素，更新队列，操作1
            deque.pollLast();
        }
        deque.add(num[i]);
        
        res.add(deque.peekFirst());  
    }
    return res;
}
}