每日算法 — 使用java实现单调队列：滑动窗口最值问题的O(n)解法

单调队列是一种巧妙地利用”单调性”来维护队列元素的数据结构。与普通队列的FIFO特性不同，单调队列保证队列中的元素始终保持单调递增或单调递减的顺序。这一特性使其成为解决滑动窗口最值问题的利器——原本需要O(nk)的暴力解法，借助单调队列可以在O(n)时间内完成。本文将用Java实现单调双端队列，并详细讲解其在多个经典算法问题中的应用。

核心思想

以滑动窗口最大值问题为例：给定数组nums和窗口大小k，求每个滑动窗口中的最大值。

暴力解法：每个窗口线性扫描求最大值，O(nk)
单调队列优化：维护一个双端队列，其中存储的是数组下标，且对应的值单调递减。

关键操作：
1. 入队前清理：新元素入队前，从队尾移除所有值小于等于新元素的元素（它们永无出头之日）
2. 出队检查：窗口滑动时，若队首元素已滑出窗口，则从队首移除
3. 取最值：队首元素即为当前窗口最大值

由于每个元素最多入队和出队各一次，总时间复杂度为O(n)。

Java完整实现

import java.util.*;

/**
 * 单调队列实现
 * 支持单调递增和单调递减两种模式
 */
public class MonotoneQueue {

    // 双端队列存储的是元素在原数组中的下标
    private Deque<Integer> deque;
    private int[] data;       // 原始数据数组
    private boolean isMax;    // true=单调递减(求最大)，false=单调递增(求最小)

    /**
     * @param data 原始数据数组
     * @param isMax true表示维护单调递减队列（用于求窗口最大值）
     */
    public MonotoneQueue(int[] data, boolean isMax) {
        this.deque = new ArrayDeque<>();
        this.data = data;
        this.isMax = isMax;
    }

    /**
     * 将元素下标index加入队列
     * 自动维护单调性
     */
    public void push(int index) {
        if (isMax) {
            // 单调递减：移除队尾所有小于等于新元素的
            while (!deque.isEmpty() && data[deque.peekLast()] <= data[index]) {
                deque.pollLast();
            }
        } else {
            // 单调递增：移除队尾所有大于等于新元素的
            while (!deque.isEmpty() && data[deque.peekLast()] >= data[index]) {
                deque.pollLast();
            }
        }
        deque.offerLast(index);
    }

    /**
     * 移除队首已过期的元素（下标小于left的元素已滑出窗口）
     */
    public void pop(int left) {
        if (!deque.isEmpty() && deque.peekFirst() < left) {
            deque.pollFirst();
        }
    }

    /**
     * 获取当前队列最值对应的下标
     */
    public int peek() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }

    /**
     * 获取当前队列最值
     */
    public int getExtreme() {
        return deque.isEmpty() ? Integer.MIN_VALUE : data[deque.peekFirst()];
    }

    public boolean isEmpty() {
        return deque.isEmpty();
    }

    // ==================== 经典问题求解 ====================

    /**
     * 问题1：滑动窗口最大值
     * LeetCode 239
     * 返回每个滑动窗口中的最大值
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) return new int[0];
        if (k == 1) return nums.clone();

        int n = nums.length;
        int[] result = new int[n - k + 1];
        MonotoneQueue mq = new MonotoneQueue(nums, true);

        for (int i = 0; i < n; i++) {
            // 移除窗口左侧滑出的元素
            mq.pop(i - k + 1);
            // 将新元素加入队列
            mq.push(i);
            // 窗口形成后开始记录结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[mq.peek()];
            }
        }

        return result;
    }

    /**
     * 问题2：滑动窗口最小值（同理）
     */
    public static int[] minSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) return new int[0];

        int n = nums.length;
        int[] result = new int[n - k + 1];
        MonotoneQueue mq = new MonotoneQueue(nums, false);

        for (int i = 0; i < n; i++) {
            mq.pop(i - k + 1);
            mq.push(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[mq.peek()];
            }
        }

        return result;
    }

    /**
     * 问题3：接雨水（Trapping Rain Water）
     * LeetCode 42
     * 使用单调栈/单调队列思想
     */
    public static int trap(int[] height) {
        if (height == null || height.length < 3) return 0;

        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        // 双指针+单调性思想
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }

        return water;
    }

    /**
     * 问题4：队列中可以看到的人数（单调递减栈变体）
     * 每个人只能看到右边比自己矮的人，直到被更高的人挡住
     */
    public static int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈

        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            // 弹出所有比自己矮的（都能看到）
            while (!stack.isEmpty() && stack.peek() < heights[i]) {
                stack.pop();
                count++;
            }
            // 如果还有更高的，也能看到那一个
            if (!stack.isEmpty()) count++;
            result[i] = count;
            stack.push(heights[i]);
        }

        return result;
    }

    /**
     * 问题5：滑动窗口最大值与最小值之差（限制子数组）
     * 求满足max-min<=limit的最长子数组长度
     */
    public static int longestSubarray(int[] nums, int limit) {
        // 分别维护最大值队列和最小值队列
        Deque<Integer> maxDeque = new ArrayDeque<>(); // 单调递减
        Deque<Integer> minDeque = new ArrayDeque<>(); // 单调递增

        int left = 0, maxLen = 0;

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

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

            // 收缩窗口直到满足条件
            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
                left++;
                if (maxDeque.peekFirst() < left) maxDeque.pollFirst();
                if (minDeque.peekFirst() < left) minDeque.pollFirst();
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }

    // ==================== 演示 ====================

    public static void main(String[] args) {
        // 演示1：滑动窗口最大值
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println("数组: " + Arrays.toString(nums));
        System.out.println("窗口大小: " + k);
        System.out.println("滑动窗口最大值: " + Arrays.toString(maxSlidingWindow(nums, k)));
        System.out.println("滑动窗口最小值: " + Arrays.toString(minSlidingWindow(nums, k)));

        // 演示2：接雨水
        int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("\n接雨水 - 高度数组: " + Arrays.toString(heights));
        System.out.println("可接雨水量: " + trap(heights));

        // 演示3：限制子数组
        int[] arr = {8, 2, 4, 7};
        int limit = 4;
        System.out.println("\n限制子数组 - 数组: " + Arrays.toString(arr) + ", limit=" + limit);
        System.out.println("最长子数组长度: " + longestSubarray(arr, limit));
    }
}

单调队列 vs 单调栈

更多应用场景

1. 最大子数组均值：二分答案 + 单调队列维护前缀和
2. DP优化：某些DP方程可转化为滑动窗口最值问题，用单调队列将O(n²)优化至O(n)
3. 单调队列优化多重背包：将物品分组后，用单调队列维护同余类中的最优值
4. 任务调度：维护时间窗口内的最高优先级任务