1 条题解

  • 0
    @ 2026-11-15 15:17:20

    题目分析

    核心观察

    把每个人的身高替换成它的排名(离散化后)。如果队列中相邻两个人的身高排名不是连续的,那么最终一定需要在这两个人之间分割一次队列。

    反过来,如果某一段队列中所有人的身高排名是连续的,那么这一段一定可以通过若干次切割和拼接操作整理成有序的形式。

    结论:答案就是「不连续的身高排名个数」,也就是把排名序列按相邻差为 ±1\pm 1 分段后,段数减 11。

    实现:从左到右扫描排名序列,维护当前这一段是递增(差为 +1+1)还是递减(差为 −1-1)。一旦当前元素既不能延续递增也不能延续递减,就开启新的一段并把答案加一。最终答案为段数减 11。

    时间复杂度 O(n)O(n)。

    需要注意第一个元素没有「前一段」,初始化时可以认为「尚未确定方向」,两种方向都允许。

    • 1

    信息

    ID
    113
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者