获取题库不需要订阅专栏，可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。

题目描述

在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，

第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j > i)。

请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。

小朋友人数范围是 [0, 40000]。

输入描述

第一行输入N，N表示有N个小朋友

第二行输入N个小朋友的身高height[i]，都是整数

输出描述

输出N个小朋友的好朋友的位置

题目解析

题目要求我们找出每个小朋友后面第一个比他高的朋友的位置，如果找不到，则输出0。由于小朋友人数可能达到40000，我们需要一个高效的算法来解决这个问题。

一个简单的方法是使用单调栈。我们遍历小朋友的身高数组，并使用一个栈来存储小朋友的索引。栈中的索引对应的小朋友身高是递减的。当我们遍历到一个小朋友时，我们不断从栈顶弹出身高比当前小朋友矮或者相等的小朋友，同时记录这些小朋友的好朋友位置为当前小朋友的索引。最后，如果栈为空或者栈顶的小朋友身高不小于当前小朋友，说明当前小朋友没有好朋友，将其好朋友位置设为0。

Java算法源码

import