239. 滑动窗口最大值
3 min
题目
解法：单调队列
思路
核心思想是使用单调递减双端队列维护窗口内元素的索引。队列中存储可能成为最大值的元素下标，且保证队头始终是当前窗口最大值。
正确性在于：当新元素加入时，移除队尾所有小于它的元素，确保队列单调递减；同时检查队头是否超出窗口范围。这样队头元素即为当前窗口最大值，且每个元素最多入队出队一次。
- Step 1: 入队前移除队尾所有小于当前元素的索引
- Step 2: 当前索引入队
- Step 3: 检查队头索引是否超出窗口左边界
- Step 4: 窗口形成后记录队头对应值
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
// 双端队列，存的是下标 维护队列内的元素对应的数值是单调递减的
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// 1. 入队前，把每一个比当前数 nums[i] 小的数从队尾踢出去
// 因为 nums[i] 进来了，前面的小个子永远不可能是最大值了
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
// 2. 当前下标入队
dq.push_back(i);
// 3. 检查队头是否已经滑出窗口
// 窗口范围是 [i - k + 1, i]，如果队头下标小于左边界，就踢出
if (dq.front() < i - k + 1) {
dq.pop_front();
}
// 4. 记录答案（当窗口完全形成后开始记录）
if (i >= k - 1) {
ans.push_back(nums[dq.front()]);
}
}
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
// 双端队列，存的是下标 维护队列内的元素对应的数值是单调递减的
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// 1. 入队前，把每一个比当前数 nums[i] 小的数从队尾踢出去
// 因为 nums[i] 进来了，前面的小个子永远不可能是最大值了
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
// 2. 当前下标入队
dq.push_back(i);
// 3. 检查队头是否已经滑出窗口
// 窗口范围是 [i - k + 1, i]，如果队头下标小于左边界，就踢出
if (dq.front() < i - k + 1) {
dq.pop_front();
}
// 4. 记录答案（当窗口完全形成后开始记录）
if (i >= k - 1) {
ans.push_back(nums[dq.front()]);
}
}
return ans;
}
};