题目描述
给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
样例
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
单调栈
模拟栈
1.栈结构:先进先出.
2.数组模拟:只对一段操作.tt表示栈顶.
C++ 代码
#include<cstdio>
#include<cstring>
const int Max_N = 1e5 + 10;
int n;
int stk[Max_N], tt;
void push(int x)
{
stk[++tt] = x;
}
void pop()
{
if( tt ) tt--;
}
bool empty()
{
return tt == 0;
}
int query()
{
return stk[tt];
}
int main()
{
scanf("%d",&n);
char op[10];
int x;
while( n-- )
{
scanf("%s",op);
if( !strcmp(op,"push") )
{
scanf("%d",&x);
push(x);
}
else if( !strcmp(op,"pop") ) pop();
else if( !strcmp(op,"empty"))
{
if( empty() ) puts("YES");
else puts("NO");
}
else
{
printf("%d\n",query());
}
}
return 0;
}
单调栈
1.首先考虑暴力做法:对于每个i,遍历j:i-1~0,若a[j]<a[i],输出j并退出循环;否则输出-1.
2.考虑计算中的冗余:对于样例3 4 2 7 5中的5来说,3,4是永远不会被考虑的,因为离5更近的位置
有一个2,也就是有如下性质的元素才会被考虑:
1)更靠右
2)更小
冗余元素:若i<j,a[i]>a=[j],则对于j右边的元素a[i]不会被考虑,冗余.也就是剩下的不冗余序列符合
序列:i<j,a[i]<a[j].(单调性)
3.实现:每次加入一个元素时,依次把序列右端更大的元素(冗余元素)删去.当不能删去的序列右端即
离a[i]最近且小于a[i]的元素.
只对右端(一端)操作,可以用栈实现.
时间复杂度
遍历O(n),插入和删除不会超过2n,所以总的时间复杂度O(n)
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10;
int n;
int a[Max_N];
int stk[Max_N], tt;
void push(int x)
{
stk[++tt] = x;
}
void pop()
{
tt--;
}
int top()
{
return stk[tt];
}
int main()
{
scanf("%d",&n);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]);
push(-1);//统一操作
for( int i = 0; i < n; i++ )
{
while( top()>=a[i] ) pop();//删除冗余元素
printf("%d ",top()); //序列中第一个<当前元素,即离ai最近且小于ai的元素
push(a[i]);
}
puts("");
return 0;
}