题解 | 滑动窗口的最大值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> res=new ArrayList<>(num.length-size+1);//初始化返回值
        if(size==0||size>num.length){
            return res;
        }//处理特殊情况
        int[]arr=new int[num.length];
        int top=0;
        int bottom=0;//初始化单调队列
        for (int i = 0; i <size; i++) {
            while (bottom>=top&&num[i]>=num[arr[bottom]]){
                bottom--;
            }//前者保证窗口大小不为负数,后者保证逻辑实现,
             //即:num[i]前面的数不严格大于num[i],那么它永远不可能成为最大值了
            arr[++bottom]=i;
        }//第一个窗口
        for (int i = size; i < num.length; i++) {
            res.add(num[arr[top]]);//top为窗口头,根据逻辑可知它是窗口内最大元素
            if(i-size>=arr[top]){
                top++;
            }//由于窗口每次只移动一位所以用if,否则用while,作用在于排除窗口外元素
            while (bottom>=top&&num[i]>=num[arr[bottom]]){
                bottom--;
            }
            arr[++bottom]=i;//添加逻辑,与上文相同
        }
        int max=Integer.MIN_VALUE;
        for(int i1 = top; i1 <= bottom; i1++){
            max=Math.max(max,num[arr[i1]]);
        }
        res.add(max);//处理最后一个窗口
        return res;
    }
}

本体关键在于维护一个在O(1)时间内找到窗口内最大值的数据结构,即单调队列.具体实现在注释中,这里不再赘述