1.什么是單調(diào)棧

• 具有單調(diào)性和棧的性質(zhì)
• 單調(diào)遞減棧就是從棧底到棧頂是單調(diào)遞減的
• 單調(diào)遞增棧就是從棧底到棧頂是單調(diào)遞增的

2.單調(diào)棧解決的問題

• 以自己為最小值，找到最長的區(qū)間；單調(diào)遞增棧
• 以自己為最大值，找到最長的區(qū)間；單調(diào)遞減棧
• 給定一個區(qū)間找到這個區(qū)間的最大值或最小值

3.單調(diào)遞減棧的性質(zhì)

• 對于第一個出棧的元素，它的右寬一定為0
• 對于第二個出棧的元素，它的右寬為第一個出棧元素的總寬
• 對于第三個出棧的元素，它的右寬為第二個出棧元素的總寬
• 。。。。。。。。
• 直到棧頂元素小于自己，才可以入棧；
• 入棧元素的左寬為上次出棧元素的總寬+1（自身）；若無出棧元素，則左寬為1（自身）
• 最后將棧中所有元素出棧，考慮所有情況

（左寬就是左邊比自己小的元素個數(shù)，右寬就是右邊比自己小的元素的個數(shù)）

4.以下面數(shù)據(jù)模擬一下單調(diào)遞減棧的操作

1入棧，無出棧元素，左寬為1；

5入棧，無出棧元素，左寬為1；

5出棧，第一個出棧右寬為0；

4入棧，左寬為上個出棧元素的總寬+1=2；

8入棧，無出棧元素，左寬為1；

8出棧，第一個出棧，右寬為0；

6入棧，左寬為上個出棧的總寬+1；

7入棧，無出棧元素，左寬為1；

7出棧，第一個出棧，右寬為0；

6出棧，第二個出棧，右寬為上個元素的總寬：1；

4出棧，第三個出棧，右寬為上個元素的總寬：3；

3入棧，左寬為上個出棧的總寬+1：6；

3出棧，第一個出棧右寬為0；

2入棧，左寬為上一個出棧的總寬+1：7；

//全部出棧：

2出棧，第一個出棧，右寬為0；

1出棧，第二個出棧的，右寬為上個出棧的總寬：7；

5.?單調(diào)棧的實現(xiàn)

hdu1506（單調(diào)遞減棧）poj2339，hrbustoj 2326（需long long）

單調(diào)遞減棧：如果是以各個元素為最大值找到最大區(qū)間的話 ?q[0]=inf, h=inf-1;

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long ll; //int a[maxn]; int q[maxn]={-1}; int w[maxn];//記錄左寬，從這個點(diǎn)之前有多少個點(diǎn)的高度大于等于當(dāng)前點(diǎn)的高度 int main() {int n,h;while(scanf("%d",&n)&&n){int top=0;ll ans=0;for(int i=1;i<=n+1;i++){if(i!=n+1)scanf("%d",&h);elseh=0;//為了讓所有元素出棧if(h>q[top])q[++top]=h,w[top]=1;else{ll cnt=0; //第一個出棧的右寬為0；while(h<=q[top]){ans=max(ans,(w[top]+cnt)*q[top]); //(左寬+右寬)*高度；cnt=cnt+w[top--]; //第(i>1)出棧的右寬為上一個的總寬；}//終于找到比自己小的數(shù)字了，可以入棧了，入棧會得到左寬，左寬為上一個出棧元素的總寬+1；q[++top]=h;w[top]=cnt+1;}}printf("%I64d\n",ans);}return 0; } //單調(diào)棧：從棧頂?shù)綏５讍握{(diào)遞減

?

總結(jié)

以上是生活随笔為你收集整理的HDU1506 / POJ2339 Largest Rectangle in a Histogram 单调递减栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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