• 重新理解了 3月13 没理解透的东西
• 完成了一道 hard
• 开始刷 Java 1000题，计划一天 30 道左右
• 实在是不想再看算法了，今天多看会业务

介绍

单调队列** 一种基于 双端队列 的数据结构，用于在滑动窗口或区间问题中高效维护最大值或最小值 它的核心思想是：

• 队列中的元素保持单调递增或单调递减；
• 插入新元素时，从队尾移除不满足单调性的元素；
• 移动窗口时，从队首移除超出范围的元素 这种结构能保证每个元素仅进出队一次，因此时间复杂度为 O(n)

题例

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值

思路解析

在这里，我们要维护一个从大到小的单调队列

代码实现

手写 Java 数组（更快

class Solution {  
    public int[] maxSlidingWindow(int[] nums, int k) {  
        int n = nums.length;  
        int[] ans = new int[n - k + 1];  // 窗口个数
        int[] q = new int[n];            // 手写队列，存入原数组的下标
        int head = 0, tail = -1;  
  
        for (int i = 0; i < n; i++) {    
            while (head <= tail && nums[q[tail]] <= nums[i]) {  
                tail--;                  // 右边出队
            }  
            q[++tail] = i;               // 右边入队
  
            int left = i - k + 1;  
            if (q[head] < left) {        // 队首离开窗口
                head++;  
            }  
            if (left >= 0) {             // 在窗口端记录答案
                ans[left] = nums[q[head]];  // 窗口最大值就在队首
            }  
        }  
        return ans;  
    }  
}

使用Deque（双端队列）以此来维护队列比较方便且好理解了，但是运行速度会慢很多 原理和上一个是一样的，但是更方便理解

首先复习一下双端队列的相关用法

操作方向	动作分类	抛异常的方法	不抛异常的方法 (推荐)	实际功能描述
队首 (First/左端)	插入	addFirst(e)	offerFirst(e)	将元素 e 塞入队列最左侧。
	删除	removeFirst()	pollFirst()	将队列最左侧的元素移除，并返回它的值。
	查看	getFirst()	peekFirst()	仅查看最左侧的元素是什么，不移除。
队尾 (Last/右端)	插入	addLast(e)	offerLast(e)	将元素 e 塞入队列最右侧。
	删除	removeLast()	pollLast()	将队列最右侧的元素移除，并返回它的值。
	查看	getLast()	peekLast()	仅查看最右侧的元素是什么，不移除。
代码实现

class Solution {  
    public int[] maxSlidingWindow(int[] nums, int k) {  
        int n = nums.length;  
        int[] ans = new int[n - k + 1];  
        Deque<Integer> q = new ArrayDeque<>();  
  
        for (int i = 0; i < n; i++) {  
        // 比较队列队尾值与即将入队值的大小 
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {  
        // 维护单调性
                q.removeLast();  
            }  
        // 将下标值添加至队尾
            q.addLast(i);  
		// 计算窗口左边界
            int left = i - k + 1;  
        // 如果最左侧元素小于左窗口边界
            if (q.getFirst() < left) {  
        // 直接移除队首元素
                q.removeFirst();  
            }  
		// 条件成立意味着窗口的成型
            if (left >= 0) {  
        // 将最大值添加至答案中
                ans[left] = nums[q.getFirst()];  
            }  
        }  
        return ans;  
    }  
}