1 条题解
-
0
题目分析
核心观察
把每个人的身高替换成它的排名(离散化后)。如果队列中相邻两个人的身高排名不是连续的,那么最终一定需要在这两个人之间分割一次队列。
反过来,如果某一段队列中所有人的身高排名是连续的,那么这一段一定可以通过若干次切割和拼接操作整理成有序的形式。
结论:答案就是「不连续的身高排名个数」,也就是把排名序列按相邻差为 分段后,段数减 。
实现:从左到右扫描排名序列,维护当前这一段是递增(差为 )还是递减(差为 )。一旦当前元素既不能延续递增也不能延续递减,就开启新的一段并把答案加一。最终答案为段数减 。
时间复杂度 。
需要注意第一个元素没有「前一段」,初始化时可以认为「尚未确定方向」,两种方向都允许。
- 1
信息
- ID
- 113
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者