分数: 233 分
问题陈述
高桥正站在远足路线的入口处。在他面前,他可以看到 N 山从前到后排成一排。的海拔 i从前面数第一座山 (1 \leq i \leq N) 是 H_i 米。
在这个问题中,我们使用以下简单模型来考虑山脉的可见性。一座山是否可见,完全取决于该山和它前面的山的相对高度。不考虑山之间的距离。
具体来说, i从前面数第一座山是 可见 当且仅当满足以下条件时:
- 对于每个整数 j 满意 1 \leq j < i, H_j < H_i 成立。
换句话说,如果前面的山中存在哪怕一座山(从 1-st 到 (i-1)-th) 其海拔为 H_i 或更大,则 i第一座山隐藏在前面的一座山后面,不可见。请注意,如果前面有一座海拔完全相同的山,那么山也是不可见的。
最前面的山( 1-st 山)始终可见,因为它前面没有山。
查找所有数字(整数来自 1 to N)高桥可见的山脉。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 所有输入值均为整数。
输入
N H_1 H_2 \ldots H_N
- 第一行包含一个整数 N 代表山脉的数量。
- 第二行包含 N 整数 H_i 以空格分隔,其中 H_i 代表海拔高度(以米为单位) i从前面数第一座山 (i = 1, 2, \ldots, N).
输出
在一行上按升序打印可见山脉的编号,并用空格分隔。尾随空格是可以接受的。
示例输入 1
5 3 1 4 1 5
示例输出 1
1 3 5
示例输入 2
8 10 20 15 25 5 30 28 35
示例输出 2
1 2 4 6 8
示例输入 3
15 100 50 80 120 110 130 125 140 200 150 180 250 240 300 299
示例输出 3
1 4 6 8 9 12 14