最近在刷 LeetCode 的時(shí)候被時(shí)間復(fù)雜度困了好久，查看別人的題解，原來用到了單調(diào)遞減棧率拒，于是詳細(xì)學(xué)習(xí)了一下記錄下來（PS：具體可參考LeetCode | 739.每日溫度）小压。
什么是單調(diào)棧玉工？
單調(diào)棧分為單調(diào)遞增棧和單調(diào)遞減棧，單調(diào)遞增棧即棧內(nèi)元素保持單調(diào)遞增的棧汁胆，同理單調(diào)遞減棧即棧內(nèi)元素保持單調(diào)遞減的棧梭姓，跟單調(diào)隊(duì)列差不多，但是只用到它的一端沦泌，利用它可以用來解決一些ACM/ICPC和OI的題目糊昙，如RQNOJ 的諾諾的隊(duì)列等。
范式：
單調(diào)遞增棧
for(int i = 0; i < T.size(); i++){
while(! stk.empty() && stk.top() > T[i]){
?stk.pop();
}
stk.push(A[i]);
}
單調(diào)遞減棧
for(int i = T.size() - 1; i >= 0; i--){
while(! stk.empty() && T[i] >= stk.top()){
stk.pop();
}
stk.push(i);
}
單調(diào)棧的作用：
可以以 O(1) 的時(shí)間復(fù)雜度得知某個(gè)位置左右兩側(cè)比他大（或行磺）的數(shù)的位置释牺，當(dāng)你需要高效率獲取某個(gè)位置左右兩側(cè)比他大（或小）的數(shù)的位置的的時(shí)候就可以用到單調(diào)棧回挽。
求解數(shù)組中元素右邊第一個(gè)比它小的元素的下標(biāo)没咙，從前往后，構(gòu)造單調(diào)遞增棧千劈；
求解數(shù)組中元素右邊第一個(gè)比它大的元素的下標(biāo)祭刚，從前往后，構(gòu)造單調(diào)遞減棧墙牌；
求解數(shù)組中元素左邊第一個(gè)比它小的元素的下標(biāo)涡驮，從后往前，構(gòu)造單調(diào)遞減棧喜滨；
求解數(shù)組中元素左邊第一個(gè)比它小的元素的下標(biāo)捉捅，從后往前，構(gòu)造單調(diào)遞增棧虽风。
總結(jié)：
以上就是單調(diào)棧的全部內(nèi)容了棒口，在刷 LeetCode 的時(shí)候寄月，每次遇到精彩的題解都會(huì)感嘆數(shù)據(jù)結(jié)構(gòu)的偉大，通過巧妙地設(shè)計(jì)无牵，無限的壓榨著計(jì)算機(jī)的潛能漾肮，對(duì)那些設(shè)計(jì)出這些數(shù)據(jù)結(jié)構(gòu)的人只剩下了膜拜！
我是「Super于」茎毁，立志做一個(gè)每天都有正反饋的人克懊！
