239. 滑动窗口最大值
type
status
date
slug
summary
tags
category
difficulty
icon
password
239. 滑动窗口最大值
给你一个整数数组
nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
示例 2：
提示：
1 <= nums.length <= 105
104 <= nums[i] <= 104
1 <= k <= nums.length
解题思路：
这道题目可以使用单调队列来解决，具体思路如下：
1. 核心数据结构
使用双端队列（deque）来维护一个单调递减的队列，队列中存储的是数组元素的下标。队首元素始终是当前滑动窗口中的最大值的下标。
2. 算法流程
- 初始化：创建一个双端队列q和结果数组res。
- 遍历数组：对数组进行一次遍历，对于每个元素：
- 清理队首：如果队首元素已经不在当前滑动窗口范围内（i - k + 1 > q.front()），将其移除。
- 维护单调性：如果当前元素大于等于队尾元素对应的数组值，则队尾元素不可能成为之后滑动窗口的最大值，将其移除。重复此步骤直到队列为空或队尾元素大于当前元素。
- 入队：将当前元素的下标加入队列。
- 更新结果：当遍历到第k-1个元素及之后，每次都将队首元素对应的数组值加入结果数组。
3. 时间复杂度分析
- 时间复杂度：O(n)，其中n为数组长度。每个元素最多被加入和弹出队列一次。
- 空间复杂度：O(k)，双端队列中最多同时存在k个元素。
4. 代码解释
vector<int> res;用于存储最终结果
deque<int> q;维护单调递减的双端队列
if(q.size() && i - k + 1 > q.front()) q.pop_front();确保队首元素在当前窗口内
while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();维护队列的单调递减性质
q.push_back(i);将当前元素下标入队
if(i >= k - 1) res.push_back(nums[q.front()]);将当前窗口的最大值加入结果数组
5. 优势
- 通过维护单调队列，我们可以在O(1)时间内获取当前窗口的最大值。
- 相比于暴力解法的O(nk)时间复杂度，该方法的O(n)时间复杂度更优。
- 相比于使用优先队列（堆）的解法，该方法不需要删除堆中已经不在窗口内的元素，实现更简单高效。
- 作者:Episkey
- 链接:https://episkey.top/article/sliding-window-maximum
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
