单调栈

题目
给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式
第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。

输出格式
共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。

数据范围
1≤N≤1051≤N≤105
1≤数列中元素≤1091≤数列中元素≤109
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
如果当前输入的x小于等于栈顶，那么x是更优解，退栈顶，直到比x小的数，那么输出栈顶就行了，最后把x加进去。

#include<iostream>
using namespace std;
const int  N=100010;
int stk[N],tt;
int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
   
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x)   tt--;//tt主要是为了判断栈是否为空
        if(tt)  cout<<stk[tt]<<' ';
        else    cout<<-1<<' ';
        stk[++tt]=x;
    }
    return 0;
    
}

用stl的stack写一下吧。。。

#include<iostream>
#include<stack>
using namespace std;
const   int N=100010;
int main()
{
   
    int n;
    cin>>n;
    stack<int>s;
    for(int i=0;i<n;i++)
    {
   
        int x;
        scanf("%d",&x);
     // if(!s.empty()) printf("top=%d\n",s.top());
        if(s.empty())
        {
   
        s.push(x);
        printf("-1 ");
        }
        else 
        {
   
        	while(!s.empty()&&s.top()>=x)	s.pop();
        	if(!s.empty())	printf("%d ",s.top());
        	else	printf("-1 ");
            s.push(x);
        }
        
        
    }
    return 0;
}