【单调队列】滑动窗口的最大值

求解代码

classMonotonicQueue{LinkedList<Integer>queue=newLinkedList<>();publicvoidpush(intn){while(!queue.isEmpty()&&queue.getLast()<n){queue.pollLast();}queue.addLast(n);}publicvoidpop(intn){if(n==queue.getFirst()){queue.pollFirst();}}publicintmax(){returnqueue.getFirst();}}publicArrayList<Integer>maxInWindows(int[]num,intsize){MonotonicQueuewindow=newMonotonicQueue();ArrayList<Integer>res=newArrayList<>();if(num==null||size<=0||num.length==0||size>num.length){returnres;}for(inti=0;i<num.length;i++){if(i<size-1){window.push(num[i]);}else{window.push(num[i]);res.add(window.max());window.pop(num[i-size+1]);}}returnres;}

小贴士

1.构建一个特殊的【单调队列】来充当不断滑动的窗口：

这个单调队列的队首记录了滑动过程中的最大值（对应max方法），从队首到队尾的元素值大小是单调递减的；

当队列为空或者尾部的元素（getLast）小于要入队的元素时，将该尾部元素弹出（pollLast）,元素是从队列尾部入队的（addLast）。

当滑动窗口需要移除的元素等于队列头部（当前最大值）时，将队首元素弹出（pollFirst）；

2.解释一下这个i-size+1

对于长度固定为size的滑动窗口，当窗口还没填满时，不考虑计算最大值和移除元素，直到把前size-1个元素填满；

从第size个元素开始（对应就是下标size-1），窗口正式填满，此时，依次完成把当前元素加入窗口，将窗口的最大值记录到res中，再把窗口最左侧的元素移除，为下一步滑动腾出一个位置。

那窗口最左侧元素的下标是什么呢？

因为当前元素是num[i]，所以此时的窗口的右边界是i，又因为窗口的大小固定为size，所以，窗口的左边界就是i-size+1，这也就是我们要移除的窗口最左侧元素的下标。