题号 NC22596
名称 Rinne Loves Data Structure
来源 牛客小白月赛11
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

你可以自己模拟一个二叉查找树——但是会TLE，因为最坏情况下它会退化成一条链。
我们想想插入当前元素的时候当前元素x可能在哪：
1：x既有后继（大于x的）又有前驱（小于x的），后继是前驱的右儿子，x是后继的左儿子或者前驱是后继的左儿子，x的前驱的右儿子——高度为前驱后继里面高度最高的+1
2：只有前驱，没有后继——前驱的高度加一
3：只有后继，没有前驱——后继的高度加一
我们只需要用有序的支持插入和查找前驱后继的数据结构（map/set）维护序列，并且用数组保存每个点的高度即可。
这道题目没有明确说明是否这n个数都是不一样的（，所以当插入的元素是一个已经出现过的元素的时候是需要特判的（严谨来说，题面应该说明这个时候应该输出什么——到底视为是插入失败还是输出已经***去的这个数的高度，但是本题没有……虽然实际上数据中没有出现相同的元素，但是确实这是题目不严谨的地方）。

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月29日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴