单调栈算法
单调栈算法
单调栈，就是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。
// 单调栈算法
#include<bits/stdc++.h>
#define reg register
using namespace std;
// 读取输入，并返回一个整数
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1; // 如果字符是负号，设置标志位为负
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48); // 将字符转换为数字并加到结果中
ch=getchar();
}
return x*f; // 返回结果
}
// 输出结果，将整数转换为字符串并打印出来
inline void write(int x){
if(x<0){
putchar('-');
x=-x; // 如果是负数，先打印负号再取反
}
if(x>9) write(x/10); // 如果数字大于9,递归调用函数处理十位数
putchar(x%10+'0'); // 打印个位数
return ;
}
const int MAXN=3000006; // 常量定义最大值
int n,ans[MAXN]; // 定义变量n和结果数组ans
vector<int > a; // 定义向量a存储输入数据
stack<int > s; // 定义栈s用于单调性判断
int main(){
n=read(); // 从输入中读取数据的数量n
a.push_back(0); // 在向量a的末尾添加一个元素0作为哨兵
for(reg int i=1;i<=n;i++) a.push_back(read()); // 从输入中读取n个数据，并添加到向量a中
for(reg int i=n;i>=1;i--){ // 从后向前遍历向量a中的元素
while(!s.empty()&&a[s.top()]<=a[i]) s.pop(); // 如果栈不为空且栈顶元素小于等于当前元素，则弹出栈顶元素直到满足条件
ans[i]=s.empty()?0:s.top(); // 如果栈为空，则结果为0,否则结果为栈顶元素，并将其压入栈中
s.push(i); // 将当前元素压入栈中
}
for(reg int i=1;i<=n;i++){ // 从后向前遍历向量a中的元素，并打印结果
write(ans[i]); // 将结果转换为字符串并打印出来
putchar(' '); // 在每个结果后面添加一个空格以便区分不同的结果
}
return 0; // 程序正常结束，返回0
}