LeetCode hot 100—滑动窗口最大值
题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例
示例 1：
输入：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 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1 输出：[1]
分析
双端队列法
双端队列是一种可以在两端进行插入和删除操作的线性数据结构。可以在 O(1) 的时间复杂度内完成队首和队尾元素的插入和删除操作，从而使得我们能够高效地维护滑动窗口内的最大值。
整体思路
对于每个元素 nums[i]：
- 移除窗口外的元素：如果队列的队首元素
window.front()等于i - k，说明该元素已经不在当前滑动窗口内，将其从队列中移除。 - 保持队列递减：从队列的队尾开始，移除所有小于当前元素
nums[i]的元素。因为这些元素不可能是后续滑动窗口中的最大值，所以可以直接移除。 - 将当前元素的索引加入队列：将当前元素的索引
i加入队列的队尾。 - 记录最大值：当
i大于等于k - 1时，说明滑动窗口的大小已经达到k，此时队列的队首元素对应的元素就是当前滑动窗口中的最大值，将其加入result中。
时间复杂度：O()
空间复杂度：O()
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
std::vector<int> result;
std::deque<int> window;
for (int i = 0; i < nums.size(); ++i) {
// 移除窗口外的元素
if (!window.empty() && window.front() == i - k) {
window.pop_front();
}
// 保持队列递减，移除小于当前元素的元素
while (!window.empty() && nums[window.back()] < nums[i]) {
window.pop_back();
}
// 将当前元素的索引加入队列
window.push_back(i);
// 当窗口大小达到 k 时，记录最大值
if (i >= k - 1) {
result.push_back(nums[window.front()]);
}
}
return result;
}
}; 知识充电
deque 容器
初始化
#include <deque>
#include <iostream>
int main() {
// 默认构造函数，创建一个空的双端队列
std::deque<int> d1;
// 构造一个包含 n 个值为 value 的元素的双端队列
std::deque<int> d2(5, 10); // 包含 5 个值为 10 的元素
// 从另一个双端队列复制元素
std::deque<int> d3(d2);
// 从迭代器范围 [first, last) 复制元素
std::deque<int> d4(d2.begin(), d2.end());
return 0;
}随机访问
#include <deque>
#include <iostream>
int main() {
std::deque<int> d = {1, 2, 3, 4, 5};
// 通过下标访问元素
std::cout << d[2] << std::endl; // 输出 3
// 通过 at() 方法访问元素，会进行边界检查，越界时抛出异常
std::cout << d.at(3) << std::endl; // 输出 4
// 访问第一个元素
std::cout << d.front() << std::endl; // 输出 1
// 访问最后一个元素
std::cout << d.back() << std::endl; // 输出 5
return 0;
}插入和删除
#include <deque>
#include <iostream>
int main() {
std::deque<int> d = {1, 2, 3};
// 在尾部插入元素
d.push_back(4); // d 变为 {1, 2, 3, 4}
// 在头部插入元素
d.push_front(0); // d 变为 {0, 1, 2, 3, 4}
// 删除尾部元素
d.pop_back(); // d 变为 {0, 1, 2, 3}
// 删除头部元素
d.pop_front(); // d 变为 {1, 2, 3}
return 0;
}当需要在队列的两端频繁进行插入和删除操作时，std::deque 是一个很好的选择，比如实现滑动窗口算法，就可以利用其在两端高效操作的特性来维护窗口内的元素。
当需要随机访问元素，但又不想像 std::vector 那样在头部插入或删除元素时性能不佳的情况，也可以使用 std::deque。