单调队列

单调队列，也可以叫做Monotonic Queue
这种数据结构主要可以优化能够用max/min heap 解决的题目，max/min heap 能够保证以nlogn的时间复杂度维持一个数组然后取出这个数组里面最大或者最小值。
下面是代码模版

public int[] monotonicQueue(int[] A, int k) {
        int n = A.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int resStart = i - k + 1;
            while (!q.isEmpty() && i - q.peekFirst() >= k) q.pollFirst();
            while (!q.isEmpty() && A[q.peekLast()] <= A[i]) q.pollLast();
            q.offerLast(i);
            q.peekFirst(); //res
        }
  return res;
}

比如力扣上面239这道题，就是要移动窗口，然后记录当前窗口的最大值，你当然可以用pq（priorityQueue)这个方法来做，就是pq.size() > k的时候把最前面的取走，然后每次到k大的时候取最大或者最小值（取决于题目的需求）然后return res
但pq的时间复杂度为nlogn，相对于单调队列来说就慢了一点，单调队列由于poll, offer, peek等操作就是O(1)的时间复杂度，然后你只需要扫一遍就可以了，所以整体来说是O(n)的复杂度。相当于是对于pq的优化。
下面是这道题的代码
239 sliding window max

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        //monotonic queue
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!q.isEmpty() && i - q.peekFirst() > k - 1) q.pollFirst(); //maintain window size
            // if upcoming number is greater than the last element in queue, pollLast element out
            // since we are maintaining a monotonic decreasing queue
            while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) q.pollLast();
            q.offerLast(i);
            if (i >= k-1) res[i-k+1] = nums[q.peekFirst()];
        }
        return res;
    }