909. 单调栈
时间限制：1000 MS 内存限制：64 MB
题目描述
# 单调栈 ## 题目描述 给定一个长度为 $N$ 的整数数列 $a_1,a_2,\ldots,a_N$，对于每个元素，找出它左侧距离它最近且严格小于它的元素，并输出该元素的值。如果不存在这样的元素，则输出 $-1$。 具体地，对于每个位置 $i$，在所有满足 $j<i$ 且 $a_j<a_i$ 的位置中，选择最大的 $j$，输出 $a_j$；如果不存在满足条件的位置，则输出 $-1$。 ## 输入格式 从文件 `monostack.in` 读入数据。 第一行包含一个整数 $N$，表示数列的长度。 第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示给定的数列。 ## 输出格式 将答案输出到文件 `monostack.out`。 输出一行，包含 $N$ 个整数，以空格分隔。第 $i$ 个整数表示 $a_i$ 左侧距离它最近且严格小于它的元素的值；如果不存在这样的元素，则为 $-1$。 ## 数据范围 - $1 \le N \le 10^5$。 - 对于所有 $1 \le i \le N$，有 $1 \le a_i \le 10^9$。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$64$ MB。 ## 样例输入 ``` 5 3 4 2 7 5 ``` ## 样例输出 ``` -1 3 -1 2 2 ```