淺談單調棧
本篇随筆簡單談一下算法競賽中的一種資料結構——單調棧。
提前說一聲，本篇随筆是一個需要前置知識的随筆。在學習單調棧之前，首先需要讀者知道什麼是棧。
這需要最基礎的資料結構知識。
然後要有不低于初二的數學素養，知道單調這個詞的含義。
也就是說正常人都差不多會。
一、單調棧的概念
單調棧。
就是前置知識加和。
單調+棧。
也就是說，對于這個單調棧來講，棧中的元素是滿足單調性的。
那麼當然有單調遞增棧和單調遞減棧等等的分類。
這就是單調棧了。
二、單調棧的應用
單調棧的概念非常簡單，那麼它的精髓就在于應用，也就是在棧上加了個單調性，它能夠支援解決的問題有什麼變化。
單調棧的應用是，維護序列中一個數左/右第一個大于/小于它的數。
你可能會說，都是\(O(N)\)複雜度，為什麼用單調棧？直接掃描就可以啦？
但是單調棧是用\(O(N)\)的時間，掃描完一整個序列并且處理出所有數左/右第一個大于/小于它的數。
直接掃描的話，複雜度明顯是\(O(N^2)\)的。
為什麼單調棧可以做到這一點呢？
假設我們要維護一個序列中所有數右側第一個大于它的數在哪。
那麼我們維護單調遞減棧，顯然，如果新入棧的元素不符合單調棧的性質，就彈棧直到它符合單調棧性質為止。在這個彈棧的過程中，顯然地，那些被彈出來的東西都比它小（廢話），而且還在它前面，也就是說，如果一個元素可以讓這個單調棧出現彈棧操作，那麼對于彈出來的所有東西來講，這個元素就是它們的答案。
這就是單調棧的妙用啦！
其應用還是比較局限的。