滑动窗口的最大值

参考力扣题解区：
用一个双端队列来充当一个滑动窗口，每次在push进去的时候都保证队首是元素最大的，max()直接拿出队首返回即可。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        MonotonicQueue window = new MonotonicQueue();
        ArrayList<Integer> res = new ArrayList<>();
        if(size > num.length || size == 0)
            return res;

        for(int i = 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]);
            }
        }

        return res;

    }

}

class MonotonicQueue{
    LinkedList<Integer> q = new LinkedList<>();
    public void push(int n){
        //保持单调递减，队首永远是最大的
        while(!q.isEmpty() && q.getLast() < n){
            q.pollLast();
        }
        q.addLast(n);
    }

    public int max(){
        return q.getFirst();
    }

    public void pop(int n){
        if(n == q.getFirst()){
            q.pollFirst();
        }
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {

        ArrayList<Integer> res = new ArrayList<>();
        if(size > num.length || size == 0 || num.length == 0)
            return res;

        int l = 0;
        int r = size-1;
        while(r <= num.length - 1){
            int max = num[l];
            for(int i = l; i <= r; i++){
                if(max < num[i]){
                    max = num[i];
                }
            }
            res.add(max);
            l++;
            r++;
        }
        return res;


    }

}