【简单】单调栈

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

输入格式

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

输出格式

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

数据范围

\rm{1} \le N \le 10^5$``$\rm{1} \le 数列中的元素 \le 10^9

输入样例

输出样例

题解

（单调栈） 数据结构 O(n)

栈即为先进后出的存储方式，先存储的数据最后弹出。单调栈即为按照存储顺序，其元素具有严格单调性的栈。要建立单调栈，就此题而言，从当前栈顶（当前栈中 x 即将为栈顶）在 x 入栈之前之前开始，如果栈不为空且比当前 x 大，那么就将其弹出，结束循环后，若栈非空则代表存在该数，将其输出，反之输出 -1 。

C++ 代码

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。