题目描述

给定一个长度为N的数组，输出每一个数左边距离它最近比它小的元素，若没有，则输出-1；

样例

5
3 4 2 7 5

-1 3 -1 2 2

算法1

模拟单调栈

单调栈是指栈里的元素都是单调有序的，当有元素需要进栈时，会比较该元素与栈顶元素，如果符合单调栈的顺序规则，则入栈，若不是，则移除栈顶元素，直至能将此元素入栈以保证栈里的顺序；
+ 以本题为例，需要维护一个严格升序数组；
+ 判断需要入栈的元素与栈顶元素的大小关系；
+ 若元素大于栈顶元素，输出栈顶元素，并入栈；
+ 若小于栈顶元素，则栈顶元素出栈，重复第二步，直到第三步或者栈空；
+ 若栈空，输出-1，将该元素入栈；

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5+10;
int a[N], top = -1;

int main()
{
    int n;
    cin>>n;
    int x;
    while(n--){
        cin>>x;
        while(top != -1 && a[top] >= x)
            --top;
        if(top == -1)   cout<<top<<' ';
        else    cout<<a[top]<<' ';
        a[++top] = x;
    }
    return 0;
}