'单调队列'

简介

oi-wiki 中对单调队列的解释是：「单调」指的是队列中元素具有某种单调性（递增或递减），而「队列」指元素只能在队头和队尾进行操作。

单调队列并不是一种新的数据结构，而是一种维护队列内部元素有序性的思想。它通常配合滑动窗口问题使用，用于在均摊 O(1) 的时间复杂度内维护区间最值。

常见形式包括：

• 单调递增队列：队头元素最小
• 单调递减队列：队头元素最大

Java实现

以下以「维护区间最大值的单调递减队列」为例进行说明。

实现要点：

1. 队列中存储的是数组下标而不是元素值，便于判断是否滑出窗口
2. 新元素入队时，从队尾删除所有比它小的元素，维持单调性
3. 队头若已经不在当前窗口范围内，需要及时弹出

示例代码如下：

import java.util.Deque;
import java.util.ArrayDeque;

public class MonotonicQueue {
    private Deque<Integer> deque = new ArrayDeque<>();

    // 入队：维护单调递减
    public void push(int[] nums, int index) {
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
            deque.pollLast();
        }
        deque.offerLast(index);
    }

    // 出队：移除滑出窗口的元素
    public void pop(int indexLimit) {
        if (!deque.isEmpty() && deque.peekFirst() < indexLimit) {
            deque.pollFirst();
        }
    }

    // 获取当前窗口最大值
    public int max(int[] nums) {
        return nums[deque.peekFirst()];
    }
}

例题

给出一个长度为 n 的数组，编程输出每 k 个连续的数中的最大值和最小值。

该问题是单调队列的经典应用，也被称为「滑动窗口最值问题」。

思路说明：

• 使用一个单调递减队列维护最大值
• 使用一个单调递增队列维护最小值
• 窗口每向右移动一步，只需对新元素入队、对过期元素出队即可

示例实现如下：

import java.util.*;

public class SlidingWindowMinMax {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        Deque<Integer> maxQ = new ArrayDeque<>();
        Deque<Integer> minQ = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // 维护最大值队列（递减）
            while (!maxQ.isEmpty() && nums[maxQ.peekLast()] <= nums[i]) {
                maxQ.pollLast();
            }
            maxQ.offerLast(i);

            // 维护最小值队列（递增）
            while (!minQ.isEmpty() && nums[minQ.peekLast()] >= nums[i]) {
                minQ.pollLast();
            }
            minQ.offerLast(i);

            // 移除滑出窗口的元素
            if (maxQ.peekFirst() <= i - k) maxQ.pollFirst();
            if (minQ.peekFirst() <= i - k) minQ.pollFirst();

            // 从第一个完整窗口开始输出结果
            if (i >= k - 1) {
                System.out.println(
                    "max=" + nums[maxQ.peekFirst()] + ", min=" + nums[minQ.peekFirst()]
                );
            }
        }
    }
}

时间复杂度分析：

• 每个元素最多入队、出队一次
• 总时间复杂度为 O(n)
• 空间复杂度为 O(k)

该题展示了单调队列在处理区间最值问题时，相比朴素枚举 O(nk) 解法的巨大优势。