1.單調堆疊簡介
單調堆疊是一種資料結構，它里邊存放的資料具有單調性，每個元素都只進堆疊一次，進堆疊時會把破壞堆疊的單調性的元素彈出，用代碼表示就是：
1 stack <int> s;//單調堆疊,單調遞增 2 int index;//要進堆疊的元素 3 while(!s.empty()&&s.top<index){ 4 5 s.pop(); 6 7 } 8 s.push(index);
彈出的元素不會再進堆疊，所以單調堆疊的復雜度為O(n)，
2.單調堆疊的功能
單調堆疊可以尋找每個元素前第一個比它大（小）的數，舉個例子，30、8、23找每個元素前第一個比它大的元素，則應用單調遞減堆疊，30入堆疊，此時它入堆疊前堆疊是空的，所以他前面沒有比它大的數，8入堆疊，此時這個堆疊的元素符合單調遞減，30不用出堆疊，8入堆疊前堆疊頂是30，所以8前面第一個比它大的數是30，23入堆疊，由于8破壞了這個堆疊的單調性，所以要出堆疊，23入堆疊前堆疊頂是30（8已出堆疊），所以23前第一個比她大的元素是30，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67298.html
標籤：C++
上一篇：結題報告
下一篇：c++中比較好用的“黑科技”