高级数据结构-单调栈
单调栈的基本应用：在一串数中，找到左边和右边最近的大于（小于）自己的数，O(n)实现。
以找最近邻大数为例，解法是维护一个单调递增的栈。假设现在有一个单调栈，从栈底至栈顶元素为A、B、C，现在要插入元素D。如果D>C,那么要讲C弹出，同时，C的右值为D,左值为B。遍历完成之后，栈中可能还会剩下一些元素，但是对于这些元素来说，因为压在自己上面的都是比自己小的数，所以他们没有最右近邻值。
理由说明：由插入顺序可知原序列为……B……C……D,如果C的右值在C-D之间，设其为x,那么由于x>C,在插入x的时候就会因为单调性的缘故而将C给弹出栈，也就不会发生D要压在C上面的情况了。同理，若B-C之间有y>B,也不会发生C压在B之上。
代码：
#include<cstdio>
#include<stack>
using namespace std;
struct node{
int L,R,v,squence;
};
node result[1000];
int main(){
stack<node> S;
int n,index,R=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&result[i].v);
result[i].squence=i;
}
for(int i=1;i<=n;i++){
while(!S.empty()&&S.top().v<result[i].v){//维持单调性而进行pop
index=S.top().squence;
result[index]=S.top();
result[index].R=i;
S.pop();
if(!S.empty()){
result[index].L=S.top().squence;
}
else result[index].L=-1;
}
S.push(result[i]);
}
while(!S.empty()){
index=S.top().squence;
result[index]=S.top();
result[index].R=R;
S.pop();
if(!S.empty()){
result[index].L=S.top().squence;
}
else result[index].L=-1;
}
for(int i=1;i<=n;i++){
printf("第%d个: 值:%d L:%d R:%d\n",i,result[i].v,result[i].L,result[i].R);
}
return 0;
}
缺陷：对于连续的相同值处理不当。这是因为我们现在的单调栈只有严格大于进和严格大于出，并把要进的数当作弹出的数的右边界导致的。这样会使栈在面对栈顶:5 要进栈元素:5的时候，将弹出的5的右边界认为是当前进栈元素5的索引。
解决方案：1.特判相等情况，使得决策推迟，相等让其进栈，例如5 5 5 5 5,然后将所有相等元素的右边界设置为与栈顶最先弹出的5的边界相等。
2.让相等且连续的数的索引压在一个空间里，节点内多加一个vector用来记录相等且连续的值的索引。
代码：
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
struct node{
int L,R,v;
};
struct store{
int v;
vector<int>squence;
};
node result[1000];
int main(){
stack<store> S;
int n,index,R=-1,len,L;
bool flag;
store val;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&result[i].v);
}
for(int i=1;i<=n;i++){
flag=false;
if(!S.empty()&&S.top().v<=result[i].v) {
while(!S.empty()&&S.top().v<=result[i].v){//维持单调性而进行pop
if(S.top().v==result[i].v){//等于的时候压进一个vector空间
S.top().squence.push_back(i);
break;
}
else{//严格小于的时候开始弹栈
flag=true;
val=S.top();
S.pop();
if(!S.empty()){
L=S.top().v;
}
else L=-1;
len=val.squence.size();
for(int j=0;j<len;j++){
result[val.squence[j]].R=result[i].v;
result[val.squence[j]].L=L;
}
}
}
if(flag){
goto label;
}
}
else {//当入栈元素更小时直接压栈
label:store New;
New.v=result[i].v;
New.squence.push_back(i);
S.push(New);
}
}
while(!S.empty()){
val=S.top();
S.pop();
if(!S.empty()){
L=S.top().v;
}
else L=-1;
len=val.squence.size();
for(int i=0;i<len;i++){
result[val.squence[i]].R=R;
result[val.squence[i]].L=L;
}
}
for(int i=1;i<=n;i++){
printf("第%d个: 值:%d L:%d R:%d\n",i,result[i].v,result[i].L,result[i].R);
}
return 0;
}