雙端隊列(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;
}