何為單調棧，顧名思義，單調棧即滿足單調性的棧結構。

單調棧解決的問題：
可以找到對于當前位置左邊(或右邊)最近的大于(或小于)它的值(或者下標)。
常用模板:

typedef long long int LL; const int N=1e6+10; LL h[N],lmax[N],rmax[N],n; //lmax[i]左邊最近的比它大的數的下標 //rmax[i]右邊最近的比它大的數的下標 void init() {stack<int>st;for(int i=1;i<=n;i++){while(st.size()&&h[st.top()]<=h[i]) st.pop();if(st.size()) lmax[i]=st.top();st.push(i);}while(st.size()) st.pop();for(int i=n;i>=1;i--){while(st.size()&&h[st.top()]<=h[i]) st.pop();if(st.size()) rmax[i]=st.top();st.push(i);} }

找最近的比它小的數的模板,和上面的幾乎一樣，只不過比較符號取相反的就行了。
入門習題:
830. 單調棧
P1901 發射站
P1823 [COI2007] Patrik 音樂會的等待
131. 直方圖中最大的矩形

總結

以上是生活随笔為你收集整理的ACM入门之【单调栈】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。