高楼视野
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题目描述】
城市里有 栋高楼,从左到右依次编号为 。第 栋楼的高度为 ,且所有楼的高度互不相同。
对于每一栋楼 ,我们想知道:从这栋楼向右看,能看到多少栋楼?具体来说,对于每个 ,请计算满足以下条件的整数 ()的数量:
- 在楼 和楼 之间(不包括楼 和楼 本身),没有比楼 更高的楼。
换句话说,楼 是从楼 向右看时“可见”的,因为中间没有任何楼挡住它。
【输入格式】
第一行包含一个整数 。
第二行包含 个整数 ,表示每栋楼的高度。
【输出格式】
输出一行,包含 个整数 ,用空格分隔。其中 表示从楼 向右看能看到的楼的数量。
【样例 1】
5
2 1 4 3 5
3 2 2 1 0
【样例 1 解释】
- 对于 (高度为 ):满足条件的 有 ,共 个。注意 不满足条件,因为在楼 和楼 之间有楼 (高度为 ),它比楼 (高度为 )更高,挡住了视线。
- 对于 (高度为 ):满足条件的 有 ,共 个。
- 对于 (高度为 ):满足条件的 有 ,共 个。
- 对于 (高度为 ):满足条件的 有 ,共 个。
- 对于 (高度为 ):右边没有楼了,所以数量为 。
【样例 2】
4
1 2 3 4
3 2 1 0
【样例 2 解释】
这是一个递增序列,每栋楼都能看到它右边的所有楼。
【样例 3】
10
1 9 6 5 2 7 10 4 8 3
2 3 3 3 2 1 2 1 1 0
【数据规模与约定】
- 对于任意 ,有