数组模拟栈
// tt表示栈顶
int stk[N], tt = 0;
stk[ ++ tt] = x;// 向栈顶插入一个数,此处用前++则tt同时表示栈内元素数量
tt -- ;// 从栈顶弹出一个数
stk[tt];// 栈顶的值
// 判断栈是否为空
if (tt ) not empty
if(!tt) empty
单调栈
单调栈即在栈的基础上使栈内元素满足递增或递减的性质
例题
给定一个长度为 N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1
输入格式
第一行包含整数 N,表示数列长度
第二行包含 N 个整数,表示整数数列
输出格式
共一行,包含 N 个整数,其中第 i个数表示数组中第 i 个数的左边第一个比它小的数,如果不存在则输出 −1
数据范围
1≤N≤1e5
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[N],tt;
int main(){
int n;
scanf("%d",&n);
while(n--){
int x;scanf("%d",&x);
while(tt&&stk[tt]>=x)tt--;//若当前栈顶元素大于x为保证x入栈后栈仍单调,要弹出栈顶元素
if(!tt)printf("-1 ");//x为最小元素或初始元素
else printf("%d ",stk[tt]);//由于此时栈单调则此时栈顶元素即满足条件的最接近的值
stk[++tt]=x;//加入x,且因为有上述操作能保证加入后栈仍是单调的
}
return 0;
}