单调栈算法

单调栈，就是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。

// 单调栈算法
#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
}