Dev.C++数据结构之单调栈：从数学上来讲，函数的单调性也可以叫做函数的增减性。当函数f(x) 的自变量在其定义区间内增大（或减小）时，函数值f(x)也随着增大（或减小），则称该函数为在该区间上具有单调性。换句话来说，函数的单调性就是在区间内的自变量只增或只减。
我们说，数学中函数在一段区间内自变量只增或只减，那么这个函数在这个区间内具有单调性。
那么，这和单调栈有什么关系呢？单调栈，你可以理解为一个升序或降序的栈。这里给出一道例题。
这道题就可以利用单调栈求解。我这里给出三个手写单调栈代码，其中有两个数组模拟单调栈，都差不多。
#include<bits/stdc++.h>
#define MAXN (int)(3e6+3e3)
using namespace std;
int n,a[MAXN],s1[MAXN],s2[MAXN],ans[MAXN],cnt=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i++){
while(a[i]>=s1[cnt]&&cnt!=0)s1[cnt]=0,s2[cnt--]=0;
if(cnt==0)ans[i]=0;
else ans[i]=s2[cnt];
s1[++cnt]=a[i];
s2[cnt]=i;
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
}
差别在于栈的数量（第二段做了空间优化），仔细看。
#include<bits/stdc++.h>
#define MAXN (int)(3e6+3e3)
using namespace std;
int n,a[MAXN],s[MAXN]，ans[MAXN],cnt=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
while(a[i]>=a[s[cnt]]&&cnt!=0)s[cnt--]=0;
if(cnt==0)ans[i]=0;
else ans[i]=s[cnt];
s[++cnt]=i;
}
for(int i=1;i<=n;i++){
printf("%d ",%ans[i]);
}
}
那第二段代码来讲吧。日常解释变量：
- n:常规变量
- a[i]：常规数组
- s[i]:压入栈中的a的下标
- ans[i]:输出数组
- cnt:栈中的元素数量
首先，为什么是n->1呢？给一个血的教训
它输出的答案与正解不搭边。
你想想：它首先有一个
if(cnt==0)ans[i]=0;else ans[i]=s[cnt];
那么输出的第一个就一定是0。
你看看样例
让我们来分析一波~~
数组的最后一项后面是不是一定都是0？而数据范围是不是1<ai<...?所以最后一项一定是0；
而初始状态cnt=0。所以输出的第一个就一定是0。故此，一定不是1->n，就只能是n->1了。能懂吧？不懂也没关系。
它不是有
if(cnt==0)ans[i]=0;else ans[i]=s[cnt];
吗？如果从后往前扫，则栈内的一定是从后往前的。而我的ans里装的是目前状态下是s，题目给的是
如果从前往后扫，新元素还没入栈，栈内的一定是这个元素以前的元素，所以只能从后往前扫，才符合这个代码。
if(cnt==0)ans[i]=0;else ans[i]=s[cnt];
可以说循环内的代码都是为了n->1而设计的。现在总懂了吧？有脑子的都能听懂。
接下来有个小坑大家得注意一下。
我就在这里在了几个跟头，注意while要加‘=’，不要像我打个‘>’或‘<’就走了。
还有注意空栈要立马跳出不要犹豫，否则就死循环了。因为空栈意味着栈内元素都为0，而数据范围我不说了，所以要有一个特判。
没有比当前元素大的给0不过多解释，然后把当前元素压入栈内，这就是完整的代码了。
最后给一下用STL的stack打的代码（抄别人的代码不是一个好习惯）我不会告诉你这是60分代码
#include<bits/stdc++.h>
#define MAXN (int)(3e6+3e3)
using namespace std;
int n,a[MAXN];
stack<int>s;
int ans[MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
while(a[i]>a[s.top()]&&cnt!=0)
{
s.pop();
}
if(cnt==0)ans[i]=0;
else ans[i]=s.top();
s.push(i);
}
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
}
建议大家少用STL，多用数组，锻炼锻炼代码能力，
最后想说：单调栈不能算是一个数据结构，本质上是一种算法，。要多理解哦！在附带转载一个简单易懂的洛谷红名dalaoMine_King的题解