廣州微網(wǎng)站建設(shè)機(jī)構(gòu),想學(xué)程序員去哪里學(xué),網(wǎng)站建設(shè)的調(diào)研報(bào)告,網(wǎng)站右側(cè)分享插件csp信奧賽C標(biāo)準(zhǔn)模板庫(kù)STL案例應(yīng)用16 deque實(shí)踐 題目描述 有一個(gè)長(zhǎng)為 nnn 的序列 aaa#xff0c;以及一個(gè)大小為 kkk 的窗口?，F(xiàn)在這個(gè)窗口從左邊開始向右滑動(dòng)#xff0c;每次滑動(dòng)一個(gè)單位#xff0c;求出每次滑動(dòng)后窗口中的最小值和最大值。 例如#xff0c;對(duì)于序列 [1…csp信奧賽C標(biāo)準(zhǔn)模板庫(kù)STL案例應(yīng)用16deque實(shí)踐題目描述有一個(gè)長(zhǎng)為n nn的序列a aa以及一個(gè)大小為k kk的窗口?，F(xiàn)在這個(gè)窗口從左邊開始向右滑動(dòng)每次滑動(dòng)一個(gè)單位求出每次滑動(dòng)后窗口中的最小值和最大值。例如對(duì)于序列[ 1 , 3 , ? 1 , ? 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7][1,3,?1,?3,5,3,6,7]以及k 3 k 3k3有如下過程窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 ? 1 3 1 [3 -1 -3] 5 3 6 7 ? 3 3 1 3 [-1 -3 5] 3 6 7 ? 3 5 1 3 -1 [-3 5 3] 6 7 ? 3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 defarraystretch{1.2} egin{array}{|c|c|c|}hline extsf{窗口位置} extsf{最小值} extsf{最大值} \ hline verb![1 3 -1] -3 5 3 6 7 ! -1 3 \ hline verb! 1 [3 -1 -3] 5 3 6 7 ! -3 3 \ hline verb! 1 3 [-1 -3 5] 3 6 7 ! -3 5 \ hline verb! 1 3 -1 [-3 5 3] 6 7 ! -3 5 \ hline verb! 1 3 -1 -3 [5 3 6] 7 ! 3 6 \ hline verb! 1 3 -1 -3 5 [3 6 7]! 3 7 \ hline end{array}窗口位置[1 3 -1] -3 5 3 6 71 [3 -1 -3] 5 3 6 71 3 [-1 -3 5] 3 6 71 3 -1 [-3 5 3] 6 71 3 -1 -3 [5 3 6] 71 3 -1 -3 5 [3 6 7]?最小值?1?3?3?333?最大值335567??輸入格式輸入一共有兩行第一行有兩個(gè)正整數(shù)n , k n,kn,k第二行有n nn個(gè)整數(shù)表示序列a aa。輸出格式輸出共兩行第一行為每次窗口滑動(dòng)的最小值第二行為每次窗口滑動(dòng)的最大值。輸入輸出樣例 1輸入 18 3 1 3 -1 -3 5 3 6 7輸出 1-1 -3 -3 -3 3 3 3 3 5 5 6 7說(shuō)明/提示【數(shù)據(jù)范圍】對(duì)于50 % 50\%50%的數(shù)據(jù)1 ≤ n ≤ 1 0 5 1 le n le 10^51≤n≤105對(duì)于100 % 100\%100%的數(shù)據(jù)1 ≤ k ≤ n ≤ 1 0 6 1le k le n le 10^61≤k≤n≤106a i ∈ [ ? 2 31 , 2 31 ) a_i in [-2^{31},2^{31})ai?∈[?231,231)。思路分析核心思想單調(diào)隊(duì)列單調(diào)隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)能在 O(1) 時(shí)間內(nèi)獲取隊(duì)列中的最值同時(shí)維護(hù)隊(duì)列的單調(diào)性。算法流程求最小值維護(hù)單調(diào)遞增隊(duì)列隊(duì)列中存儲(chǔ)元素的索引而不是值本身維護(hù)隊(duì)列使得隊(duì)首到隊(duì)尾對(duì)應(yīng)的值單調(diào)遞增每次滑動(dòng)窗口移除隊(duì)首超出窗口范圍的元素從隊(duì)尾移除比當(dāng)前元素大的元素保持單調(diào)性將當(dāng)前元素索引加入隊(duì)尾當(dāng)窗口形成時(shí)輸出隊(duì)首對(duì)應(yīng)的值求最大值維護(hù)單調(diào)遞減隊(duì)列與最小值類似但維護(hù)隊(duì)首到隊(duì)尾對(duì)應(yīng)的值單調(diào)遞減從隊(duì)尾移除比當(dāng)前元素小的元素時(shí)間復(fù)雜度O(n)每個(gè)元素最多入隊(duì)出隊(duì)一次因此總時(shí)間復(fù)雜度為 O(n)。代碼實(shí)現(xiàn)#includebits/stdc.husingnamespacestd;constintMAXN1e65;inta[MAXN];intmain(){intn,k;cinnk;for(inti0;in;i){cina[i];}dequeintdq;// 雙端隊(duì)列存儲(chǔ)元素索引// ---------- 求最小值 ----------for(inti0;in;i){// 移除隊(duì)首超出窗口范圍的元素// 如果隊(duì)首索引小于等于 i-k說(shuō)明該元素已不在當(dāng)前窗口中while(!dq.empty()dq.front()i-k){dq.pop_front();}// 維護(hù)單調(diào)遞增隊(duì)列從隊(duì)首到隊(duì)尾a[索引]遞增// 從隊(duì)尾開始移除所有大于等于當(dāng)前元素 a[i] 的索引// 因?yàn)檫@些元素不可能成為后續(xù)窗口的最小值有更小的 a[i]while(!dq.empty()a[dq.back()]a[i]){dq.pop_back();}// 將當(dāng)前索引加入隊(duì)尾dq.push_back(i);// 當(dāng)窗口完全進(jìn)入數(shù)組后開始輸出已經(jīng)處理了至少 k 個(gè)元素// 此時(shí)隊(duì)首元素就是當(dāng)前窗口的最小值if(ik-1){couta[dq.front()] ;}}coutendl;// 清空隊(duì)列準(zhǔn)備求最大值dq.clear();// ---------- 求最大值 ----------for(inti0;in;i){// 同樣先移除超出窗口的元素while(!dq.empty()dq.front()i-k){dq.pop_front();}// 維護(hù)單調(diào)遞減隊(duì)列從隊(duì)首到隊(duì)尾a[索引]遞減// 從隊(duì)尾開始移除所有小于等于當(dāng)前元素 a[i] 的索引// 因?yàn)檫@些元素不可能成為后續(xù)窗口的最大值有更大的 a[i]while(!dq.empty()a[dq.back()]a[i]){dq.pop_back();}dq.push_back(i);// 輸出當(dāng)前窗口的最大值if(ik-1){couta[dq.front()] ;}}coutendl;return0;}功能分析數(shù)據(jù)結(jié)構(gòu)選擇deque雙端隊(duì)列能在兩端進(jìn)行插入刪除操作符合單調(diào)隊(duì)列需求存儲(chǔ)索引而非值便于判斷元素是否在窗口內(nèi)也方便獲取對(duì)應(yīng)值兩個(gè)關(guān)鍵維護(hù)操作窗口范圍維護(hù)while(!dq.empty()dq.front()i-k){dq.pop_front();}確保隊(duì)列中所有元素都在當(dāng)前窗口內(nèi)只需檢查隊(duì)首因?yàn)殛?duì)列是按時(shí)間順序加入的單調(diào)性維護(hù)最小值移除隊(duì)尾所有 ≥ a[i] 的元素最大值移除隊(duì)尾所有 ≤ a[i] 的元素保證隊(duì)列的單調(diào)性質(zhì)隊(duì)首就是當(dāng)前窗口的最值輸出時(shí)機(jī)當(dāng)i k-1時(shí)窗口完全進(jìn)入數(shù)組可以輸出結(jié)果。此時(shí)共有n-k1個(gè)窗口。算法優(yōu)勢(shì)高效每個(gè)元素最多入隊(duì)出隊(duì)一次O(n) 時(shí)間復(fù)雜度空間優(yōu)化只需 O(k) 的額外空間通用性強(qiáng)模板化代碼適用于各種滑動(dòng)窗口最值問題示例分析以輸入[1,3,-1,-3,5,3,6,7]k3為例最小值隊(duì)列變化i0(1): 隊(duì)列[0] → 無(wú)輸出i1(3): 隊(duì)列[0,1] → 無(wú)輸出i2(-1): 移除1隊(duì)列[0,2] → 輸出 a[2]-1i3(-3): 移除2隊(duì)列[3] → 輸出 a[3]-3i4(5): 隊(duì)列[3,4] → 輸出 a[3]-3i5(3): 移除4隊(duì)列[3,5] → 輸出 a[3]-3i6(6): 移除3隊(duì)列[5,6] → 輸出 a[5]3i7(7): 隊(duì)列[5,6,7] → 輸出 a[5]3完整系列資料請(qǐng)查看專欄《csp信奧賽C標(biāo)準(zhǔn)模板庫(kù)STL》https://blog.csdn.net/weixin_66461496/category_13108077.html各種學(xué)習(xí)資料助力大家一站式學(xué)習(xí)和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奧賽知識(shí)! ##########;cout############# 沖刺信奧賽拿獎(jiǎng)! #############;cout###### 課程購(gòu)買后永久學(xué)習(xí)不受限制! ######;return0;}一、CSP信奧賽C通關(guān)學(xué)習(xí)視頻課C語(yǔ)法基礎(chǔ)C語(yǔ)法進(jìn)階C算法C數(shù)據(jù)結(jié)構(gòu)CSP信奧賽數(shù)學(xué)CSP信奧賽STL二、CSP信奧賽C競(jìng)賽拿獎(jiǎng)視頻課信奧賽csp-j初賽高頻考點(diǎn)解析CSP信奧賽C復(fù)賽集訓(xùn)課12大高頻考點(diǎn)專題集訓(xùn)三、考級(jí)、競(jìng)賽刷題題單及題解GESP C考級(jí)真題題解CSP信奧賽C初賽及復(fù)賽高頻考點(diǎn)真題解析CSP信奧賽C一等獎(jiǎng)通關(guān)刷題題單及題解詳細(xì)內(nèi)容1、csp/信奧賽C完整信奧賽系列課程永久學(xué)習(xí)https://edu.csdn.net/lecturer/7901 點(diǎn)擊跳轉(zhuǎn)2、CSP信奧賽C競(jìng)賽拿獎(jiǎng)視頻課https://edu.csdn.net/course/detail/40437 點(diǎn)擊跳轉(zhuǎn)3、csp信奧賽沖刺一等獎(jiǎng)有效刷題題解CSP信奧賽C初賽及復(fù)賽高頻考點(diǎn)真題解析持續(xù)更新https://blog.csdn.net/weixin_66461496/category_12808781.html 點(diǎn)擊跳轉(zhuǎn)2025 csp-j 復(fù)賽真題及答案解析最新更新2025 csp-x(山東) 復(fù)賽真題及答案解析最新更新2025 csp-x(河南) 復(fù)賽真題及答案解析最新更新2025 csp-x(遼寧) 復(fù)賽真題及答案解析最新更新2025 csp-x(江西) 復(fù)賽真題及答案解析最新更新2025 csp-x(廣西) 復(fù)賽真題及答案解析最新更新2020 ~ 2024 csp 復(fù)賽真題題單及題解2019 ~ 2022 csp-j 初賽高頻考點(diǎn)真題分類解析2021 ~ 2024 csp-s 初賽高頻考點(diǎn)解析2023 ~ 2024 csp-x (山東)初賽真題及答案解析2024 csp-j 初賽真題及答案解析2025 csp-j 初賽真題及答案解析最新更新2025 csp-s 初賽真題及答案解析最新更新2025 csp-x (山東)初賽真題及答案解析(最新更新)2025 csp-x (江西)初賽真題及答案解析(最新更新)2025 csp-x (遼寧)初賽真題及答案解析(最新更新)CSP信奧賽C一等獎(jiǎng)通關(guān)刷題題單及題解持續(xù)更新https://blog.csdn.net/weixin_66461496/category_12673810.html 點(diǎn)擊跳轉(zhuǎn)129 道刷題練習(xí)和詳細(xì)題解涉及模擬算法、數(shù)學(xué)思維、二分算法、 前綴和、差分、深搜、廣搜、DP專題、 樹和圖4、GESP C考級(jí)真題題解GESP(C 一級(jí)二級(jí)三級(jí))真題題解持續(xù)更新https://blog.csdn.net/weixin_66461496/category_12858102.html 點(diǎn)擊跳轉(zhuǎn)GESP(C 四級(jí)五級(jí)六級(jí))真題題解持續(xù)更新https://blog.csdn.net/weixin_66461496/category_12869848.html 點(diǎn)擊跳轉(zhuǎn)· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟著王老師一起學(xué)習(xí)信奧賽C;cout 成就更好的自己 ;cout csp信奧賽一等獎(jiǎng)屬于你! ;return0;}