//這是19號的話~拖了一天了
以后不能隨便發(fā)pyp了//??
我們還是很水的役听，hduoj做到最后腦殼疼
現在還是先把今天看的單調棧做個小小的總結叭
今天先以HDU 1506為例
定義
單調遞增或單調減的棧，跟單調隊列差不多表窘，但是只用到它的一端典予，利用它可以用來解決一些ACM/ICPC和OI的題目，如RQNOJ 的諾諾的隊列等乐严。
單調棧是一種特殊的棧瘤袖，特殊之處在于棧內的元素都保持一個單調性。
假設下圖是一個棧內元素的排列情況(單調遞增的棧)：
此時插入情況有兩種：
(1).插入元素大于棧頂元素
當插入7時昂验，因7 > 6捂敌，滿足單調遞增的條件，故可以直接加入棧
此時：
(2).插入的元素小于棧頂元素
當插入3時既琴，為了滿足單調遞增棧的性質占婉，需要先將棧頂的4，6彈出甫恩，再插入逆济，此時：
結論
利用單調棧，可以找到從左/右遍歷第一個比它小/大的元素的位置
栗子來啦：
假設有一個單調遞增的棧 S和一組數列：
a : 5 3 7 4
用數組L[i] 表示 第i個數向左遍歷的第一個比它小的元素的位置
如何求L[i]？
首先我們考慮一個樸素的算法奖慌，可以按順序枚舉每一個數霎终，然后再依此向左遍歷。
但是當數列單調遞減時升薯，復雜度是嚴格的O(n^2)莱褒。
此時我們便可以利用單調棧在O(n)的復雜度下實現
我們按順序遍歷數組，然后構造一個單調遞增棧
(1). i = 1時涎劈，因棧為空广凸，L[1] = 0，此時再將第一個元素的位置下標1存入棧中
此時棧中情況：
(2).i = 2時蛛枚，因當前3小于棧頂元素對應的元素5谅海，故將5彈出棧
此時棧為空
故L[2] = 0
然后將元素3對應的位置下標2存入棧中
此時棧中情況：
(3).i = 3時，因當前7大于棧頂元素對應的元素3蹦浦，故
L[3] = S.top() = 2 (棧頂元素的值)
然后將元素7對應的下標3存入棧
此時棧中情況：
(4).i = 4時扭吁，為保持單調遞增的性質，應將棧頂元素3彈出 （我認為他這里的3是說第三個也就是元素7盲镶，不然就不對了）
此時 L[4] = S.top() = 2;
然后將元素4對應的下標3存入棧
此時棧中情況：
對應的結果：
a : 5 3 7 4
L : 0 0 2 2
總結：
一個元素向左遍歷的第一個比它小的數的位置就是將它插入單調棧時棧頂元素的值侥袜，若棧為空，則說明不存在這么一個數溉贿。然后將此元素的下標存入棧枫吧，就能類似迭代般地求解后面的元素
實現
1.最基礎的應用就是給定一組數，針對每個數宇色，尋找它和它右邊第一個比它大的數之間有多少個數九杂。
2.給定一序列，尋找某一子序列宣蠕，使得子序列中的最小值乘以子序列的長度最大例隆。
3.給定一序列，尋找某一子序列抢蚀，使得子序列中的最小值乘以子序列所有元素和最大镀层。
代碼模板
Stack<int> S;
for(int i=1 ;i<=n ;i++){
while(S.size() && a[S.top()] >= a[i]) S.pop();
if(S.empty()) L[i] = 0;
else L[i] = S.top();
S.push(i);
}
例題:HDU 1506
首先考慮最大面積的矩形X的左右邊界的性質：
設其左邊界為L，右邊界為R思币，則其高H = min{h[i] | L <= i <= R}
此時最大面積為 (R - L + 1) * H
若此時左邊界的左邊那個矩形的高度 h[L-1] >= H
則左邊界可以向左拓展鹿响，則新的面積為：
(R - (L-1) + 1) * H > 原面積
則與原假設條件沖突
故左邊界左邊的那個矩形的高度 :h[L-1] < H
同理右邊界右邊的那個矩形的高度： h[R+1] < H
設H = h[i]
所以左邊界L是滿足h[j-1] < h[i]的最大的j羡微，即從i點向左遍歷的第一個高度比i小的點的右邊一個點
而右邊界R是滿足 h[j+1] < h[i]的最小的j谷饿，即從i點向右遍歷第一個高度比i小的點的左邊一個點
所以我們可以利用單調棧的性質得到每個確定點，即確定高度的最大面積矩形的左右邊界妈倔，然后枚舉取最大即可博投。
現在最主要的問題是（R[i]-L[i]）是對應下標為i的矩形的寬度，那R[i] 和 L[i]分別表示什么盯蝴？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 這些做法可以學習
//typedef unsigned long long ull;
const int N= 100000+100;
stack<int>S;
ll h[N]; //這里的ll要小心毅哗，不然就會wrong
int R[N],L[N];
//L和R都是用來儲存坐標听怕，我要他從小到大排序，如果遇到了一個小的虑绵，就將之前比他大的全部出棧
int main()
{
int n;
freopen("data","r",stdin);
while(cin>>n&&n>0){
for(int i=0;i<n;i++)
cin>>h[i];
while(S.size()) S.pop();
for(int i=0;i<n;i++){
while(S.size()&&h[S.top()]>=h[i])
S.pop();
if(S.empty()) L[i]=0;
else L[i]=S.top()+1;
S.push(i);
}
for(int i=0;i<n;i++)
cout<<L[i];
while(S.size()) S.pop();
for(int i=n-1;i>=0;i--){
while(S.size()&&h[S.top()]>=h[i])
S.pop();
if(S.empty()) R[i]=n;
else R[i]=S.top(); //為什么這個不用+1尿瞭，因為i所對應的位置就是棧頂此刻對應的位置，無形中已經+1
S.push(i);
}
for(int i=0;i<n;i++)
cout<<R[i];
ll ans=0;
for(int i=0;i<n;i++)
ans=max(ans,h[i]*(R[i]-L[i]));
cout<<ans<<endl;
}
return 0;
}
關于模板我剛開始不理解這道題翅睛，就去借鑒了一下https://blog.csdn.net/zuzhiang/article/details/78134247 結果發(fā)現他對這道題的代碼并不是很能理解声搁，而且感覺他少了一邊。然后又回來了這個代碼
其實L和R記錄的是元素i向左向右最長能到達的那個元素捕发，可能再-1疏旨，這是開區(qū)間閉區(qū)間的區(qū)別。
假*單調棧
后來參考了一下師兄的簡書扎酷，學會了一個假*單調棧
就拿這個例題的樣例為例叭
input 2 1 4 5 1 3 3
先默認每個數的最左邊就是左邊的那個數檐涝，但是一旦遇到一個更小的數，它的左邊界就不僅僅是左邊最靠近它的那個數了法挨，這時得循環(huán)谁榜，它可能是左邊的左邊界，甚至一直左邊界下去凡纳，比如：L[5]=1惰爬，所以L[5]=L[L[5]]，而L[5]其實就是下標4惫企，向左移一位嘛撕瞧，同理R的話是向右移一位。
代碼如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
ll L[100001],R[100001],h[100001];
int main()
{
long long int n;
freopen("data","r",stdin);
while(scanf("%lld",&n)&&n){
for(int i=1;i<=n;i++)
scanf("%lld",&h[i]);
for(int i=1;i<=n;i++){
L[i]=i-1;
R[i]=i+1;
}
for(int i=1;i<=n;i++)
while(L[i]&&h[L[i]]>=h[i])
L[i]=L[L[i]];
for(int i=n;i>0;i--)
while(R[i]<=n&&h[R[i]]>=h[i])
R[i]=R[R[i]];
long long int sum=0;
for(int i=1;i<=n;i++)
sum=sum>(h[i]*(R[i]-L[i]-1))?sum:(h[i]*(R[i]-L[i]-1));
printf("%lld\n",sum);
}
return 0;
}
義無反顧入坑
- n狞尔，h丛版，R，L要是long long 型
- sum=sum>(h[i](R[i]-L[i]-1))?sum:(h[i](R[i]-L[i]-1));這個如果不確定的話可以自己去瞎掰模擬一下//雖然會浪費時間
