優先隊列和單調隊列(雙端隊列實現的)

這里寫自定義目錄標題

  • 一、優先隊列與單調隊列
  • 二、優先隊列
    • 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;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/903255.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/903255.shtml
英文地址,請注明出處:http://en.pswp.cn/news/903255.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

如何在idea中寫spark程序

在 IntelliJ IDEA 中編寫 Spark 程序是一個高效且便捷的方式&#xff0c;以下是一個詳細的步驟指南&#xff0c;幫助你在 IntelliJ IDEA 中創建和運行 Spark 程序。 一、環境準備 安裝 Java&#xff1a; 確保已經安裝了 JDK 1.8 或更高版本。可以通過以下命令檢查&#xff1a;…

BERT BERT

BERT ***** 2020年3月11日更新&#xff1a;更小的BERT模型 ***** 這是在《深閱讀的學生學得更好&#xff1a;預訓練緊湊模型的重要性》&#xff08;arXiv:1908.08962&#xff09;中提到的24種較小規模的英文未分詞BERT模型的發布。 我們已經證明&#xff0c;標準的BERT架構和…

SpringBoot啟動警告:OpenJDK 64-Bit Server VM warning

問題描述 以Debug模式啟動Spring boot項目之后&#xff0c;日志打印&#xff1a;OpenJDK 64-Bit Server VM warning: Sharing is only supported for boot loader classes because bootstrap classpath has been appended&#xff0c; 警告信息 解決方案&#xff1a;配置VM opt…

“該虛擬機似乎正在使用中“

當某一天打開虛擬機突然彈出"該虛擬機似乎正在使用中"。 遇到這種問題的解決方法很簡單&#xff0c;出現這種問題是因為錯誤關閉虛擬機導致&#xff0c;當我們點擊獲取所有權時發現不能解決問題。這里分享一種簡單的解決方法。 打開虛擬機的文件目錄 找到lck文件夾下…

【CSS】層疊,優先級與繼承(三):超詳細繼承知識點

目錄 繼承一、什么是繼承&#xff1f;2.1 祖先元素2.2 默認繼承/默認不繼承 二、可繼承屬性2.1 字體相關屬性2.2 文本相關屬性2.3 列表相關屬性 三、不可繼承屬性3.1 盒模型相關屬性3.2 背景相關屬性 四、屬性初始值4.1 根元素4.2 屬性的初始值4.3 得出結論 五、強制繼承5.1 in…

Android LiveData關鍵代碼

1、observer方法 public void observe(NonNull LifecycleOwner owner, NonNull Observer<? super T> observer) {assertMainThread("observe");if (owner.getLifecycle().getCurrentState() DESTROYED) {// ignorereturn;}LifecycleBoundObserver wrapper …

Docker-高級使用

前言 書接上文Docker-初級安裝及使用_用docker安裝doccano-CSDN博客&#xff0c;我們講解了Docker的基本操作&#xff0c;下面我們講解的是高級使用&#xff0c;請大家做好準備&#xff01; 大家如果是從初級安裝使用過來的話&#xff0c;建議把之前鏡像和搭載的容器數據卷里面…

Spring Boot常用注解詳解:實例與核心概念

Spring Boot常用注解詳解&#xff1a;實例與核心概念 前言 Spring Boot作為Java領域最受歡迎的快速開發框架&#xff0c;其核心特性之一是通過注解&#xff08;Annotation&#xff09;簡化配置&#xff0c;提高開發效率。注解驅動開發模式讓開發者告別繁瑣的XML配置&#xff…

TRO再添新案 TME再拿下一熱門IP,涉及Paddington多個商標

4月2日和4月8日&#xff0c;TME律所代理Paddington & Company Ltd.對熱門IP Paddington Bear帕丁頓熊的多類商標發起維權&#xff0c;覆蓋文具、家居用品、毛絨玩具、紡織用品、游戲、電影、咖啡、填充玩具等領域。跨境賣家需立即排查店鋪內的相關產品&#xff01; 案件基…

經驗分享-上傳ios的ipa文件

.ipa格式的二進制文件&#xff0c;是打包后生成的文件&#xff0c;無論我們是放上去testflight測試還是正式上傳到app store&#xff0c;都需要先上傳到蘋果開發者中心的app store connect上的構建版本上。 在app store connect上&#xff0c;上傳構建版本的功能&#xff0c;它…

docker(3) -- 圖形界面

1. 前言 在wsl(8) – 圖形界面文章中介紹了wsl2默認是支持圖形界面的&#xff0c;現在我們嘗試下在docker中運行gui程序試試看。 2. x11-apps 啟動一個docker&#xff0c;安裝一些gui小程序&#xff0c;然后運行&#xff0c;發現會失敗。ubuntu_base詳見文章wsl(6) – 安裝d…

Docker容器跑定時任務腳本

最近搞了一個Docker容器跑腳本&#xff0c;想設置一個定時任務&#xff0c;每天8點運行一次&#xff0c;結果死活不成功。排查了一天&#xff0c;有一點當局者迷了&#xff0c;明明時間是對的&#xff0c;明明時區是對的&#xff0c;定時任務也是啟動的&#xff0c;它就是不執行…

【Linux】什么是完全限定域名

FQDN 是 “完全限定域名” (Fully Qualified Domain Name) 的縮寫。 FQDN 是一個互聯網上特定計算機或主機的完整且唯一的域名。它詳細說明了該主機在域名系統 (DNS) 層級結構中的確切位置。 一個 FQDN 通常由以下幾個部分組成&#xff0c;從左到右依次是&#xff1a; 主機名…

小結:BFD

*BFD&#xff08;雙向轉發檢測&#xff0c;Bidirectional Forwarding Detection&#xff09;是一種快速、輕量級的故障檢測機制&#xff0c;用于檢測網絡中兩點之間的連通性。它廣泛應用于各種場景 1. 檢測 IP 鏈路 應用場景&#xff1a; BFD 用于檢測兩臺設備之間的 IP 層連…

配置Spark歷史服務器,輕松查看任務記錄

在大數據處理中&#xff0c;Spark是一個強大的分布式計算框架。但當Spark服務重啟后&#xff0c;之前的運行記錄就會消失&#xff0c;給我們排查問題和分析任務執行情況帶來不便。這時&#xff0c;配置Spark歷史服務器就顯得尤為重要&#xff0c;它能幫助我們保存和查看歷史任務…

(六)RestAPI 毛子(外部導入打卡/游標分頁/Refit/Http resilience/批量提交/Quartz后臺任務/Hateoas Driven)

文章目錄 項目地址一、外部導入打卡功能1.1 創建實體1. Entry實體2. EntryImport實體3. 添加數據庫配置4. 創建表 1.2 創建DTOs1.3 創建GetEnties Controller 二、游標分頁2.1 創建所需要的DTOs1. 創建游標分頁的請求參數2. 創建CollectionResponse3. 添加游標編碼和解碼的DTO …

Node.js CSRF 保護指南:示例及啟用方法

解釋 CSRF 跨站請求偽造 (CSRF/XSRF) 是一種利用用戶權限劫持會話的攻擊。這種攻擊策略允許攻擊者通過誘騙用戶以攻擊者的名義提交惡意請求,從而繞過我們的安全措施。 CSRF 攻擊之所以可能發生,是因為兩個原因。首先,CSRF 攻擊利用了用戶無法辨別看似合法的 HTML 元素是否…

Flink介紹——實時計算核心論文之Dataflow論文總結

數據流處理的演變與 Dataflow 模型的革新 在大數據處理領域&#xff0c;流式數據處理系統的發展歷程充滿了創新與變革。從早期的 S4 到 Storm&#xff0c;再到 MillWheel&#xff0c;每一個系統都以其獨特的方式推動了技術的進步。S4 以其無中心架構和 PE&#xff08;Processi…

Arduino 入門學習筆記(五):KEY實驗

Arduino 入門學習筆記&#xff08;五&#xff09;&#xff1a;KEY實驗 開發板&#xff1a;正點原子ESP32S3 例程源碼在文章頂部可免費下載&#xff08;審核中…&#xff09; 1. GPIO 輸入功能使用 1.1 GPIO 輸入模式介紹 在上一文章中提及到 pinMode 函數&#xff0c; 要對…

Centos9安裝docker

1. 卸載docker 查看是否安裝了docker yum list | grep docker卸載老版本docker&#xff0c;拷貝自官網 sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine卸載新版本…