文章目录
- 双端队列(deque)详解
- 基本特性
- 常用操作
- 1. 构造和初始化
- 2. 元素访问
- 3. 修改操作
- 4. 容量操作
- 性能特点
- 时间复杂度：
- 空间复杂度：
- 滑动窗口最大值
- 题目描述
- 方法思路
- 解决代码
双端队列(deque)详解
双端队列(deque，全称double-ended queue)是C++标准模板库(STL)中的一个容器适配器，它允许在队列的两端高效地进行插入和删除操作。
基本特性
- 双向操作：可以在队列的前端和后端进行插入(push)和删除(pop)操作
- 随机访问：支持通过索引直接访问元素(类似vector)
- 动态大小：可以根据需要自动调整大小
- 不连续存储：与vector不同，deque的元素不一定是连续存储的
常用操作
1. 构造和初始化
#include <deque>// 空deque
deque<int> dq1;// 包含n个元素的deque，初始值为0
deque<int> dq2(5); // {0, 0, 0, 0, 0}// 包含n个元素的deque，初始值为value
deque<int> dq3(5, 10); // {10, 10, 10, 10, 10}// 通过初始化列表构造
deque<int> dq4 = {1, 2, 3, 4, 5};// 通过迭代器范围构造
deque<int> dq5(dq4.begin(), dq4.begin()+3); // {1, 2, 3}
2. 元素访问
deque<int> dq = {1, 2, 3, 4, 5};// 使用下标运算符访问
int a = dq[2]; // 3// 使用at()方法访问(会检查边界)
int b = dq.at(3); // 4// 访问第一个和最后一个元素
int front = dq.front(); // 1
int back = dq.back(); // 5
3. 修改操作
deque<int> dq = {1, 2, 3};// 在末尾添加元素
dq.push_back(4); // {1, 2, 3, 4}// 在开头添加元素
dq.push_front(0); // {0, 1, 2, 3, 4}// 删除末尾元素
dq.pop_back(); // {0, 1, 2, 3}// 删除开头元素
dq.pop_front(); // {1, 2, 3}// 在指定位置插入元素
auto it = dq.begin() + 1;
dq.insert(it, 5); // {1, 5, 2, 3}// 删除指定位置元素
it = dq.begin() + 2;
dq.erase(it); // {1, 5, 3}// 清空deque
dq.clear(); // {}
4. 容量操作
deque<int> dq = {1, 2, 3};// 检查是否为空
bool isEmpty = dq.empty(); // false// 获取元素数量
size_t size = dq.size(); // 3// 调整大小
dq.resize(5); // {1, 2, 3, 0, 0}
dq.resize(2); // {1, 2}
性能特点
时间复杂度：
- 随机访问：O(1)
- 在开头或结尾插入/删除：O(1)
- 在中间插入/删除：O(n)
空间复杂度：
- 比vector占用更多内存，因为需要维护多个内存块
- 但不需要像vector那样在扩容时复制所有元素
滑动窗口最大值
题目描述
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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
Example 2:
Input: nums = [1], k = 1
Output: [1]
这是一个经典的滑动窗口问题，我们需要找到数组中每个大小为k的滑动窗口中的最大值。
方法思路
我们可以使用双端队列(deque)来高效解决这个问题。主要思路是维护一个双端队列，队列中存储的是数组元素的索引，且队列中的元素按照从大到小的顺序排列。这样可以保证队列前端始终是当前窗口的最大值。
具体步骤如下：
- 遍历数组中的每个元素
- 移除队列中不在当前窗口范围内的元素索引
- 移除队列中所有小于当前元素的索引，因为它们不可能是当前或未来窗口的最大值
- 将当前元素索引加入队列
- 当窗口形成后(即
i >= k-1)，将队列前端元素对应的值加入结果
解决代码
#include <vector>
#include <deque>using namespace std;vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;deque<int> dq; // 存储的是索引for (int i = 0; i < nums.size(); ++i) {// 移除不在窗口范围内的元素索引while (!dq.empty() && dq.front() <= i - k) {dq.pop_front();}// 移除所有小于当前元素的索引while (!dq.empty() && nums[dq.back()] < nums[i]) {dq.pop_back();}// 添加当前元素索引dq.push_back(i);// 当窗口形成后，添加结果if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;
}
