发表于 2024.05.16

• 首先对所有的车按位置从大到小排序，以获得有序的位置信息。不难得知，每个车队的速度都以车头(即距离更大者)为准，也即车和车队之间的比较只要以车头为准。因此，可以使用两个变量分别维护当前所处理车队的车头起始位置和速度，按位置顺序遍历所有的车辆，如果当前车辆能在target之前赶上该车队(的车队)，则将其合并在同一个车队中；否则(要么速度不够，要么追上时已经在target之后了)，以该车作为车头新建一个车队即可，并跳至新车队的处理，而旧车队后面不会有其他车跟上了(因为后面的车追上去后，只能以新车队的车头的速度继续前进，而这个车头本来就追不上旧车队)。

  class Solution:
      def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
          car_infos = sorted(zip(position, speed), key=lambda item: -item[0])  # 按距离倒序排序
          cur_fleet_head_pos, cur_fleet_head_speed = car_infos[0]
          ans = 1
          for i in range(1, len(car_infos)):
              pos, spd = car_infos[i]
              if (cur_fleet_head_speed >= spd
                      or (cur_fleet_head_pos - pos) / (spd - cur_fleet_head_speed) > (target - cur_fleet_head_pos) / cur_fleet_head_speed):  # 追不上现有车头
                  ans += 1
                  cur_fleet_head_pos = pos
                  cur_fleet_head_speed = spd
          return ans

• LC 题目链接