239.滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

思路：一次遍历，每次快速找出窗口最大值，关键在于快速，此时不能再考虑遍历窗口的方法

使用单调队列，队尾插入队首出，保持队首最大，每次窗口移动时更新队列（新元素入队，旧元素出队），则当前窗口最大值就是此时队首元素

更新队列包括插入和删除。1）插入时将nums[i]与队尾元素比较，若nums[i] > 队尾，则弹出队尾，直到队列有合适nums[i]的位置为止（为什么不用插入？因为插入涉及元素的挪动，而我们只关心队首是什么，因此无关紧要的元素直接丢弃）

2）删除：因为只考虑队首，所以只有当删除的元素等于队首时才需要操作，将队首弹出

因为需要头插和尾插，数据结构考虑使用java的LinkedList

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < k-1) {
                //先填满窗口的前 k - 1
                window.push(nums[i]);
            } else {
                // 窗口右边界右移，加入新数字
                window.push(nums[i]);
                // 记录此时窗口最大值
                res.add(window.max());
                // 窗口左边界左移，删除旧数字
                window.pop(nums[i-k+1]);
            }
        }
        // 结果转换为数组
        int [] arr = new int [res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }
}
// 单调队列数据结构
class MonotonicQueue {
    // 双链表，支持头部和尾部增删元素
    private LinkedList<Integer> q = new LinkedList<>();
    // 操作1：向队列加入一个元素
    public void push(int n) {
        // 将前面小于自己的元素都删除
        while (!q.isEmpty() && q.getLast() < n) {
            q.pollLast();  // 移除队尾元素
        }
        q.addLast(n);  // 加入队尾
    }
    // 操作2：返回队列中最大值
    public int max() {
        // 队头的元素肯定是最大的
        return q.getFirst();
    }
    // 操作1：删除队列中指定元素
    public void pop(int n) {
        if (n == q.getFirst()) {
            q.pollFirst();
        }
    }
}