最新华为OD机试真题-找朋友(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎 在线评测链接

找朋友(100分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎀 找朋友

题目描述

在学校中， 个小朋友站成一队，第 个小朋友的身高为 。每个小朋友都在寻找自己的好朋友，他们的好朋友是指在队伍中站在自己后面第一个比自己高的小朋友。如果第 个小朋友找到了好朋友，那么他的好朋友就是第 个小朋友（要求 ）。

现在请你帮忙生成一份列表，列表中的第 个位置表示第 个小朋友的好朋友的位置。如果第 个小朋友找不到好朋友，那么在列表的第 个位置上填 。

输入格式

第一行包含一个正整数 ，表示小朋友的人数。

第二行包含 个正整数，用空格分隔，第 个数表示第 个小朋友的身高 。

输出格式

输出一行，包含 个正整数，用空格分隔，第 个数表示第 个小朋友的好朋友的位置。如果第 个小朋友找不到好朋友，则输出 。

样例输入 1

2
100 95

样例输出 1

0 0

样例输入 2

8
123 124 125 121 119 122 126 123

样例输出 2

1 2 6 5 5 6 0 0

数据范围

题解

我们可以从左到右遍历每个小朋友，对于第 个小朋友，我们从 开始向右寻找第一个身高比他高的小朋友，如果找到了，就将该小朋友的位置记录在结果列表的第 个位置上；如果找不到，就在结果列表的第 个位置上记录 。

遍历完所有小朋友后，我们就得到了每个小朋友的好朋友的位置。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

n = int(input())
heights = list(map(