什么是單調(diào)棧?有什么好處?
就是棧中元素，按遞增順序或者遞減順序排列的時(shí)候，
單調(diào)棧的最大好處就是時(shí)間復(fù)雜度是線性的，每個(gè)元素遍歷一次！
單調(diào)棧是一種數(shù)據(jù)結(jié)構(gòu)，它里邊存放的數(shù)據(jù)具有單調(diào)性，每個(gè)元素都只進(jìn)棧一次，進(jìn)棧時(shí)會把破壞棧的單調(diào)性的元素彈出。
為了描述方便，以下舉例及偽代碼以維護(hù)一個(gè)整數(shù)的單調(diào)遞增棧為例。
1. 過程
插入
將一個(gè)元素插入單調(diào)棧時(shí)，為了維護(hù)棧的單調(diào)性，需要在保證將該元素插入到棧頂后整個(gè)棧滿足單調(diào)性的前提下彈出最少的元素。
例如，棧中自頂向下的元素為{0,11,45,81}。
插入元素14時(shí)為了保證單調(diào)性需要依次彈出元素0,11，操作后棧變?yōu)閧14,45,81}。
用偽代碼描述如下：
insert x while !sta.empty() && sta.top()<x sta.pop() sta.push(x)
2. 使用
自然就是從棧頂讀出來一個(gè)元素，該元素滿足單調(diào)性的某一端。
例如取出的即棧中的最小值。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習(xí)題和答疑，點(diǎn)擊了解：
一點(diǎn)編程也不會寫的：零基礎(chǔ)C語言學(xué)練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進(jìn)階課程
從零到寫出一個(gè)爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程：算法競賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程