单调队列（Monotonic Queue）

单调队列是一种主要用于解决滑动窗口类问题的数据结构，即在长度为 n n n的序列中，求每个长度为 m m m的区间的区间最值。他的时间复杂度为 O ( n ) O(n) O(n)。

基本思想

单调队列的基本思想是维护一个双向队列，遍历序列，仅当一个元素称为某一个区间最值时保留它。

案例

举个例子，寻找 [ i − 3 , i ] [i-3,i] [i−3,i]窗口的最小值为：

代码实现

其的核心代码为：

public class Template {
          
   
    public void template(int[] nums, int m) {
          
   
        int n = nums.length;
        int[] ans = new int[n];
        Deque<Integer> dq = new LinkedList<>();

        for (int i = 0; i < n; i++) {
          
   
            if (!dq.isEmpty() && i - dq.peekFirst() >= m) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i]) dq.pollLast();
            dq.addLast(i);
            if (i >= m - 1) System.out.printf("%d ", nums[dq.peekFirst()]);
        }
    }

    public static void main(String[] args) {
          
   
        Template template = new Template();
        template.template(new int[]{
          
   7, 6, 8, 12, 9, 10, 3}, 4);// 输出 6 6 8 3
    }
}

参考文献：