知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 滑动窗口最大值 ## 题目(LeetCode 239) 给定数组和窗口大小 k,返回每个窗口中的最大值。 ``` 输入:nums=[1,3,-1,-3,5,3,6,7], k=3 输出:[3,3,5,5,6,7] ``` ## 大白话理解 暴力做法每个窗口都扫一遍找最大值,O(nk)。用单调队列优化到 O(n)。 单调队列:队列里的元素从大到小排列。新元素进来时,把队尾比它小的都踢掉(它们不可能再成为最大值了)。 ``` 窗口 [1,3,-1]:队列 [3,-1],最大值 = 队头 3 窗口 [3,-1,-3]:队列 [3,-1,-3],最大值 = 队头 3 窗口 [-1,-3,5]:5 进来,踢掉 -3 和 -1,队列 [5],最大值 = 5 ``` ## 代码 ```java public int[] maxSlidingWindow(int[] nums, int k) { 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) ## 一句话总结 单调递减队列,队头永远是当前窗口的最大值。新元素进来踢掉比它小的,过期的从队头移除。 --- 上一篇:[05 - 长度最小的子数组](./05-min-subarray-len.md) | 下一篇:[07 - 字符串的排列](./07-permutation-in-string.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入