【單調(diào)棧】

1.原理

單調(diào)棧，就是棧內(nèi)元素保持一定單調(diào)性（單調(diào)遞增或單調(diào)遞減）的棧，即從棧底到棧頂單調(diào)遞增或遞減。

對于單調(diào)遞增的棧，如果棧為空或入棧元素值大于等于棧頂元素值，則入棧；否則，若入棧會破壞棧的單調(diào)性，因此需要將比入棧元素大的元素全部出棧。

對于單調(diào)遞減的棧，如果棧為空或入棧元素值小于等于棧頂元素值，則入棧；否則，若入棧會破壞棧的單調(diào)性，因此需要將比入棧元素小的元素全部出棧。

以下圖單調(diào)遞減的棧為例，從棧頂?shù)綏５壮跏荚貫?#xff1a;6、4、2、1

當插入的元素小于等于棧頂元素時，滿足單調(diào)遞減的條件，可直接加入棧，例如：插入元素 0，可直接加到棧頂

當插入的元素大于等于棧頂元素時，為滿足單調(diào)遞減的性質(zhì)，需要從棧頂開始，將比入棧元素小的值全部彈出再入棧，例如：插入元素 3，需要先將 1、2 彈出

2.應(yīng)用

單調(diào)棧常用的應(yīng)用有：

• 給定一組數(shù)，對于某個數(shù)，找到從左/右遍歷第一個比它小/大的元素的位置
• 給定一組數(shù)，針對每個數(shù)，尋找其與其左/右第一個比它小/大的數(shù)之間有多少個數(shù)
• 給定一序列，尋找某一子序列，使得子序列中的最小值乘以子序列的長度最大
• 給定一序列，尋找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大

3.實現(xiàn)

1）單調(diào)遞增棧

stack<int> S;for(int i=1;i<=n;i++){while(!S.empty()&&a[S.top()]>a[i]){//棧不為空且棧頂元素大于入棧元素時S.pop();//將棧頂大于入棧元素的元素出棧...//更新結(jié)果}S.push(i);//元素入棧 }

2）單調(diào)遞減棧

stack<int> S;for(int i=1;i<=n;i++){while(!S.empty()&&a[S.top()]<a[i]){//棧不為空且棧頂元素小于入棧元素時S.pop();//將棧頂小于入棧元素的元素出棧...//更新結(jié)果}S.push(i);//元素入棧 }

【單調(diào)隊列】

1.原理

單調(diào)隊列就是從隊首到隊尾滿足單調(diào)性的隊列，與單調(diào)棧極其相似，其基本原理與單調(diào)棧相同，只需將單調(diào)棧先進后出的性質(zhì)改為先進先出的性質(zhì)即可。?

對于單調(diào)遞增的隊列，若隊列為空或入隊元素 x 大于等于隊尾元素，則入隊；否則，入隊會破壞隊列的單調(diào)性，因此需要將隊尾中比入隊元素 x 大的元素全部出隊。

對于單調(diào)遞減的隊列，若隊列為空或入隊元素 x 小于等于隊尾元素，則入隊；否則，入隊會破壞隊列的單調(diào)性，因此需要將隊尾中比入隊元素 x 小的元素全部出隊。

2.應(yīng)用

單調(diào)隊列的常用應(yīng)用有：

• 給出一組數(shù)，求這組數(shù)中第一個大/小于等于一個數(shù) x 的數(shù)
• 維護單調(diào)性，從而解決區(qū)間內(nèi)最小/大的問題
• 解決滑動窗口問題
• 優(yōu)化多重背包 DP、斜率優(yōu)化?DP

3.實現(xiàn)

單調(diào)隊列一般使用 STL 的 deque(雙端隊列) 實現(xiàn)即可，由于雙端隊列即可再隊首操作又可在隊尾操作，那么這樣的性質(zhì)就彌補了單調(diào)棧只可在尾端操作的不足，使得首段也有了一定的限制。

1）單調(diào)遞增隊列

deque<int> Q://雙端隊列 for(int i=1;i<=n;i++){while((!Q.empty())&&Q.back()>A[i]){//隊列不為空且隊尾元素大于入隊元素時Q.pop_back();//將隊列尾端大于入隊元素的元素出隊...//更新結(jié)果}q.push_back(A[i]);//元素入隊...//更新結(jié)果 }

2）單調(diào)遞減隊列?

deque<int> Q://雙端隊列 for(int i=1;i<=n;i++){while((!Q.empty())&&Q.back()<A[i]){//隊列不為空且隊尾元素小于入隊元素時Q.pop_back();//將隊列尾端小于入隊元素的元素出隊...//更新結(jié)果}q.push_back(A[i]);//元素入隊...//更新結(jié)果 }

【例題】

• City Skyline（POJ-3044）(單調(diào)棧)：點擊這里
• Bad Hair Day（POJ-3250）(單調(diào)棧)：點擊這里
• Largest Rectangle in a Histogram（HDU-1506）(左右兩次單調(diào)棧)：點擊這里
• Passing the Message（HDU-3410）(左右兩次單調(diào)棧)：點擊這里
• Non-negative Partial Sums（HDU-4193）(單調(diào)隊列)：點擊這里
• Second My Problem First（HDU-3706）(單調(diào)隊列)：點擊這里
• Beauty Of Unimodal Sequence（HDU-6592）(LIS+單調(diào)棧)：點擊這里

總結(jié)

以上是生活随笔為你收集整理的线性结构 —— 单调栈与单调队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。