单调队列

239. 滑动窗口最大值

存在一种这样的场景：快速得到 n 个元素中的最大值，而且这 n 个元素还在不断的变化中！

题目详情可见 滑动窗口最大值

数据结构实现

基于上述的场景，我们构造出了一种新的数据结构：单调队列

每次把新元素都从队尾插入，而队头的元素永远的最大的。如果要删除某一个元素时，我们判断是否为队头元素，如果不是，则不删；否则删除队头元素

该数据结构的具体方法如下：

public class MonotonicQueue {
    // 双链表，支持头部和尾部增删元素
    private final LinkedList<Integer> q = new LinkedList<>();
    // 在队尾添加元素 n
    public void push(int n);
    // 队头元素如果是 n，删除它
    public void pop(int n);
    // 返回当前队列中最大值
    public int max();
}

如下图所示。每当我们调用push(n)时，对于元素 3, 2, 1 将会被删掉，元素 4 接到 元素 5 的后面

具体实现如下：

// 在队尾添加元素 n
public void push(int n) {
    // 将小于 n 的元素全部删除
    while (!q.isEmpty() && q.getLast() < n) {
        q.pollLast();
    }
    // 然后将 n 加入尾部
    q.addLast(n);
}

如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max 方法可以可以这样写：

// 返回当前队列中最大值
public int max() {
    return q.getFirst();
}

pop(n)方法在队头删除元素n，也很好写：

// 队头元素如果是 n，删除它
public void pop(int n) {
    if (n == q.getFirst()) {
        q.pollFirst();
    }
}

至此，对于数据结构MonotonicQueue的全部方法已经实现

实战题目

现在我们回到本文开头提到的题目，直接使用我们自己实现的数据结构就很好解决了。具体代码如下：

public int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        // 填满 k - 1 个元素
        if (i < k - 1) window.push(nums[i]);
        else {
            // 窗口向前移动一格
            window.push(nums[i]);
            list.add(window.max());
            window.pop(nums[i - k + 1]);
        }
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}