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

import java.util.*;


public class Solution {
    // 单调队列使用双端队列来实现
    private ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
    // 入队的时候，last方向入队，但是入队的时候
    // 需要保证整个队列的数值是单调的
    // (在这个题里面我们需要是递减的)
    // 并且需要注意，这里是Q.getLast() < val
    // 如果写成Q.getLast() <= val就变成了严格单调递增
    private void push(int val) {
        while (!Q.isEmpty() && Q.getLast() < val) {
            Q.removeLast();
        }
        // 将元素入队
        Q.addLast(val);
    }
    // 出队的时候，要相等的时候才会出队
    private void pop(int val) {
        if (!Q.isEmpty() && Q.getFirst() == val) {
            Q.removeFirst();
        }
    }
   public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> ans = new ArrayList<>();
        if(size==0||size>num.length) return ans;
        for (int i = 0; i < num.length; i++) {
            push(num[i]);
            // 如果队列中的元素还少于k个
            // 那么这个时候，还不能去取最大值
            if (i < size - 1) {
                continue;
            }
            // 队首元素就是最大值
            ans.add(Q.getFirst());
            // 尝试去移除元素
            pop(num[i - size + 1]);
        }
        // 将ans转换成为数组返回!
        return ans;
    }
}