單調(diào)棧和單調(diào)隊(duì)列
- 單調(diào)棧
找到每個(gè)數(shù)左邊離這個(gè)數(shù)最近的數(shù)
這種數(shù)據(jù)結(jié)構(gòu)適用的提醒似乎只有單調(diào)棧問題。
// 暴力做法
for(int i = 0; i<n ;i++){
for(int j = i-1; j>=0 ;j--){
if(a[j]<a[i]){
cout << a[j] << " ";
break;
}else{
cout << "-1" << " ";
}
}
}
單調(diào)棧做法蓖康，由于兩個(gè)數(shù)之間存在一種特殊的大小關(guān)系，在比較的時(shí)候可以就刪掉不合格的數(shù)蒜焊，使得最終棧中的數(shù)滿足一個(gè)單調(diào)升序關(guān)系。其實(shí)就是讓暴力做法里棧中的無序數(shù)一直刪刪刪直到變成有序棧泳梆。棧中存放數(shù)是有序的
#include <iostream>
using namespace std;
const int N = 10e5+10;
int stk[N],n,tt;
int main(){
ios::sync_with_stdio(false); // 優(yōu)化cin輸入榜掌，但是只能提升一點(diǎn)點(diǎn)
cin.tie(0); // 這個(gè)也能優(yōu)化輸入輸出
// 還是推薦使用scanf和printf 會(huì)顯著提升，大約10倍
cin >> n;
for(int i = 0;i<n;i++){
int x;
cin >> x;
while(tt && stk[tt] >= x) tt--; // 棧如果不為空的話憎账，當(dāng)前棧頂?shù)脑厝羰翘蟮脑挘旬?dāng)前元素彈出棧鼠哥，一直到棧頂?shù)脑乇葂嚴(yán)格小
if(tt){
cout << stk[tt] << " ";
}else{
cout << -1 << " ";
}
stk[++tt] = x; // 每一輪做完之后熟菲，把當(dāng)前元素放入棧頂
}
return 0;
}
- 單調(diào)隊(duì)列
典型應(yīng)用：求滑動(dòng)窗口里面的最大值或者最小值
由于窗口的特性，因此窗口問題中的窗口都可以使用隊(duì)列來維護(hù)抄罕。類似單調(diào)棧，把沒有用的元素刪掉呆贿，看看有沒有得到單調(diào)性
拿求滑動(dòng)窗口最小值來說，窗口里的最右邊的數(shù)是最新進(jìn)來的做入，只要最右邊的數(shù)的左邊的數(shù)比該數(shù)大，就可以把所有左邊的數(shù)給刪掉（因?yàn)樽钣疫叺臄?shù)已經(jīng)是最小竟块，我們的目的就是求最小）一直要?jiǎng)h除到使得隊(duì)列中的數(shù)保持遞增浪秘，這樣隊(duì)列有序的話，隊(duì)列頭就是最小值耸携，隊(duì)列尾就是最大值
總結(jié)：?jiǎn)握{(diào)棧和單調(diào)隊(duì)列都是讓數(shù)據(jù)結(jié)構(gòu)里的數(shù)據(jù)通過刪除一直保持單調(diào)有序
拿數(shù)組模擬的隊(duì)列和棧相比最大的好處就是 快 ！STL的隊(duì)列和棧就沒有那么快
但是實(shí)際應(yīng)用中STL編譯的時(shí)候夺衍，我們會(huì)開優(yōu)化，開完之后其實(shí)速度跟數(shù)組模擬的隊(duì)列差不多快
O2優(yōu)化實(shí)際上是Optimize沟沙，2是優(yōu)化等級(jí)。除了O2優(yōu)化還有O3優(yōu)化尝胆，這是更高等級(jí)的優(yōu)化；還有Ofast含衔、Os等等多種優(yōu)化等級(jí)二庵，對(duì)于有些算法題，使用暴力算法+O2優(yōu)化是可以正常AC的催享；但是注意并不是所有O2優(yōu)化都是正優(yōu)化，有的會(huì)是負(fù)優(yōu)化
[gcc官方關(guān)于O2優(yōu)化的說明] (https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)
/*
輸出滑動(dòng)窗口中的最大值和最小值
*/
#include <iostream>
using namespace std;
const int N = 10e6+10;
int n,k;
int a[N],q[N]; // a數(shù)組是存儲(chǔ)數(shù)值本身因妙，b數(shù)組是存儲(chǔ)數(shù)值對(duì)應(yīng)的下標(biāo)
int main(){
scanf("%d%d",&n,&k);
for(int i = 0; i<n;i++){
scanf("%d",&a[i]);
}
int hh = 0,tt = -1; // 初始化隊(duì)列 隊(duì)列實(shí)質(zhì)上就是數(shù)組加兩個(gè)變量
for(int i = 0; i<n;i++){ // 遍歷每一個(gè)數(shù)
// 1.檢查隊(duì)頭是否劃出窗口
if(tt >= hh && i-k+1>q[hh] ){ // 沒有的話
hh++;
}
// 2.當(dāng)前值a[i]與隊(duì)尾值比較 隊(duì)尾值太大就要出隊(duì) 因?yàn)橐獜男〉酱笈? while(tt >= hh && a[i]<a[q[tt]]) tt--;
q[++tt] = i; // 把當(dāng)前值得下標(biāo)放入q[]中
// 3. 打印這個(gè)窗口中的最小值 需要窗口在數(shù)組里才會(huì)輸出
if(i - k + 1 >= 0) printf("%d ",a[q[hh]]);
}
cout << endl;
hh = 0,tt = -1;
for(int i = 0; i<n;i++){
if(tt >= hh && i-k+1>q[hh] ){
hh++;
}
// .當(dāng)前值a[i]與隊(duì)尾值比較 隊(duì)尾值太小就要出隊(duì) 因?yàn)橐獜男〉酱笈? while(tt >= hh && a[i] > a[q[tt]]) tt--;
q[++tt] = i;
if(i - k + 1 >= 0) printf("%d ",a[q[hh]]);
}
return 0;
}
