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

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        // 存 数组元素的下标 单调双端队列!
        Deque<Integer> deque = new LinkedList<>();
        int l = 0, r = size;
        // 第一组!
        for(int i = 0; i < r; i++){
            while(!deque.isEmpty() && num[deque.peekLast()] < num[i])
                deque.pollLast();
            deque.offer(i);
        }
        
        while(r < num.length){ 
            // 将上一个窗口中最大的值ans 加入list 不用pollFirst 因为不确定是否这个值还属于下一个窗口!
            list.add(num[deque.peekFirst()]);
            // 去除已经不属于窗口范围的值!
            while(!deque.isEmpty() && deque.peekFirst() <= l) deque.pollFirst();
            // 保证队列的单调性! (单调递减!)
            while(!deque.isEmpty() && num[deque.peekLast()] < num[r]) deque.pollLast();
            // 将这个位置添加到队列尾部!
            deque.offer(r);
            
            // 窗口向后移动!
            r++;
            l++;
        }
        // 最后一组!
        list.add(num[deque.pollFirst()]);
        return list;
    }
}