【LeetCode Hot100】 滑动窗口最大值[特殊字符]单调队列，Java实现！图解+代码，小白也能秒懂！

💻 [LeetCode Hot100] 滑动窗口最大值🔥单调队列，Java实现！图解+代码，小白也能秒懂！

✏️本文对应题目链接：滑动窗口最大值

---

📌 题目描述

给定一个整数数组 nums 和一个整数 k，请你在数组中滑动一个大小为 k 的窗口，返回每次滑动时窗口中的最大值。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

---

🧠 解题思路（图文分解）

❗ 核心难点

如何在O(n)时间复杂度内找到每个滑动窗口的最大值？

---

方法一：单调队列（黄金思路）✨

关键步骤：

1. 初始化：
   • 使用双端队列 deque 存储窗口中的元素索引
   • 保证队列中的元素按从大到小排列
2. 遍历数组：
   • 移除队列中不在当前窗口范围内的索引
   • 移除队列中所有小于当前元素的索引
   • 将当前元素索引加入队列
   • 如果窗口形成（i >= k - 1），则将队列头部元素作为当前窗口的最大值
3. 返回结果：所有窗口的最大值

---

图解单调队列

输入数组：

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

步骤1：初始化

deque = []
result = []

步骤2：遍历数组

i=0: nums[0]=1 → deque=[1] → 窗口未形成
i=1: nums[1]=3 → 移除1 → deque=[3] → 窗口未形成
i=2: nums[2]=-1 → deque=[3,-1] → 窗口形成 → result=[3]
i=3: nums[3]=-3 → deque=[3,-1,-3] → 窗口形成 → result=[3,3]
i=4: nums[4]=5 → 移除3,-1,-3 → deque=[5] → 窗口形成 → result=[3,3,5]
i=5: nums[5]=3 → deque=[5,3] → 窗口形成 → result=[3,3,5,5]
i=6: nums[6]=6 → 移除5,3 → deque=[6] → 窗口形成 → result=[3,3,5,5,6]
i=7: nums[7]=7 → 移除6 → deque=[7] → 窗口形成 → result=[3,3,5,5,6,7]

最终结果：

result = [3, 3, 5, 5, 6, 7]

---

🚀 代码实现

class Solution {public int[] maxSlidingWindow(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]; // 结果数组Deque<Integer> deque = new ArrayDeque<>(); // 双端队列for (int i = 0; i < n; i++) {// 移除不在当前窗口范围内的索引while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}// 移除队列中所有小于当前元素的索引while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}// 将当前元素索引加入队列deque.offerLast(i);// 如果窗口形成，则将队列头部元素作为当前窗口的最大值if (i >= k - 1) {result[i - k + 1] = nums[deque.peekFirst()];}}return result;}
}

---

💡 复杂度分析

• 时间复杂度：O(n) → 每个元素最多入队和出队一次
• 空间复杂度：O(k) → 双端队列最多存储 k 个元素

---

方法二：动态规划（优化空间复杂度）

关键思路：将数组分成大小为 k 的块，分别计算从左到右和从右到左的最大值。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums == null || nums.length == 0 || k <= 0) {return new int[0];}int n = nums.length;int[] leftMax = new int[n];int[] rightMax = new int[n];int[] result = new int[n - k + 1];// 从左到右计算leftMaxfor (int i = 0; i < n; i++) {if (i % k == 0) {leftMax[i] = nums[i];} else {leftMax[i] = Math.max(leftMax[i - 1], nums[i]);}}// 从右到左计算rightMaxfor (int i = n - 1; i >= 0; i--) {if (i == n - 1 || (i + 1) % k == 0) {rightMax[i] = nums[i];} else {rightMax[i] = Math.max(rightMax[i + 1], nums[i]);}}// 计算每个窗口的最大值for (int i = 0; i < n - k + 1; i++) {result[i] = Math.max(rightMax[i], leftMax[i + k - 1]);}return result;}
}

---

🌟 总结要点

✅ 单调队列核心思想：维护一个递减的队列，快速获取窗口最大值
✅ 动态规划优化：适用于大数据量，但实现较复杂
✅ 适用场景：滑动窗口问题、区间最值问题

---