這里寫自定義目錄標題
- 一、優先隊列與單調隊列
- 二、優先隊列
- 2.1 概念
- 2.2 增刪查 + 判空
- 2.3 示例代碼
- 三、雙端隊列
- 四、單調隊列
- 4.1 單調遞增隊列
- 4.2 單調遞減隊列
一、優先隊列與單調隊列
二、優先隊列
2.1 概念
一種特殊的隊列,它與普通隊列的主要區別在于元素的出隊順序是根據元素的優先級來決定的,而不是按照元素進入隊列的順序。具體來說,優先隊列中的元素具有優先級,優先級較高的元素會比優先級較低的元素先被移除。
原理: 大根堆(默認大根堆)或者小根堆。
2.2 增刪查 + 判空
1.增: push()
2.刪: pop()
3.查: top()
4.元素個數: size()
5.判空: empty()
2.3 示例代碼
#include <iostream>
#include <queue>int main() {// 創建一個優先隊列,默認使用最大堆std::priority_queue<int> pq;// 向優先隊列中插入元素pq.push(10);pq.push(5);pq.push(20);pq.push(15);pq.pop();// 輸出并刪除優先隊列中的元素(按優先級高低)while (!pq.empty()) {std::cout << pq.top() << " "; // 輸出堆頂元素pq.pop(); // 刪除堆頂元素}//15 10 5return 0;
}
三、雙端隊列
- 增:push_back() / push_front()
- 刪:pop_back() / pop_front()
- 查:back() / front() / at() / []
- 判空:size() / empty()
#include <iostream>
#include <deque>using namespace std;int main() {// 創建一個雙端隊列deque<int> dq;// 向隊列兩端插入元素dq.push_front(10); // 前端插入 10dq.push_back(20); // 后端插入 20dq.push_front(5); // 前端插入 5dq.push_back(30); // 后端插入 30//5 10 20 30// 輸出隊列的大小cout << "隊列的大小: " << dq.size() << endl;// 訪問隊列的前端和后端元素cout << "隊列前端元素: " << dq.front() << endl;cout << "隊列后端元素: " << dq.back() << endl;// 刪除隊列前端和后端的元素dq.pop_front(); // 刪除前端元素dq.pop_back(); // 刪除后端元素//10 20// 輸出刪除后的隊列cout << "刪除后的隊列: ";for (auto it = dq.begin(); it != dq.end(); ++it) {cout << *it << " ";}cout << endl;// 使用 at() 訪問元素cout << "索引 0 處的元素: " << dq.at(0) << endl;// 使用下標運算符訪問元素cout << "索引 0 處的元素: " << dq[0] << endl;// 檢查隊列是否為空if (dq.empty()) {cout << "隊列為空" << endl;} else {cout << "隊列不為空" << endl;}// 清空隊列dq.clear();cout << "清空后的隊列大小: " << dq.size() << endl;return 0;/*隊列的大小: 4隊列前端元素: 5隊列后端元素: 30刪除后的隊列: 10 20 索引 0 處的元素: 10索引 0 處的元素: 10隊列不為空清空后的隊列大小: 0*/
}
四、單調隊列
一般是基于雙端隊列(deque)實現的
應用:滑動窗口,區間最值方法。
4.1 單調遞增隊列
1.概念
- 隊列中的元素按從小到大的順序排列。
- 每次插入新元素時,保證隊列的元素保持遞增順序。如果新元素小于隊列中的某些元素,則刪除這些元素,直到新元素大于隊列的尾部元素。
示例
vector<int> minSlidingWindow(vector<int>& nums, int k) {vector<int> result;deque<int> dq; // 單調遞增隊列for (int i = 0; i < nums.size(); i++) {// 移除不在窗口中的元素if (!dq.empty() && dq.front() < i - k + 1) {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;
}
4.2 單調遞減隊列
1.概念
- 隊列中的元素按從大到小的順序排列。
- 每次插入新元素時,保證隊列的元素保持遞減順序。如果新元素大于隊列中的某些元素,則刪除這些元素,直到新元素小于隊列的尾部元素。
示例
vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;deque<int> dq; // 單調遞減隊列for (int i = 0; i < nums.size(); i++) {// 移除不在窗口中的元素if (!dq.empty() && dq.front() < i - k + 1) {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;
}