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

双端队列，打败2.33%

public class Solution {
    class node{
        int index;
        int val;
        public node(int index,int val){
            this.index = index;
            this.val = val;
        }
    }
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        Deque<node> q = new LinkedList<>(); 
        ArrayList<Integer> ans = new ArrayList<>();
        if(size==0||size>num.length)return ans;
        for(int i=0;i<size;i++){
            while(!q.isEmpty()&&q.getLast().val < num[i]){
                q.pollLast();
            }
            q.offerLast(new node(i,num[i]));
        }
       
        ans.add(q.getFirst().val);
        for(int i=size;i<num.length;i++){
            while(!q.isEmpty()&&q.getFirst().index<=i-size){
                q.pollFirst();
            }
            while(!q.isEmpty()&&q.getLast().val < num[i]){
                q.pollLast();
            }
            q.offerLast(new node(i,num[i]));
            ans.add(new Integer(q.getFirst().val));
        }
        return ans;
        
    }
}