LeetCode 853. Car Fleet问题栈解法调试求助

错误原因分析 #

你的代码核心问题在于未按车辆初始位置从近到远排序，导致追及逻辑完全错误：

• 车队的形成依赖车辆的前后位置：后方车辆（position更小，离target更远）只能追赶前方车辆（position更大，离target更近），无法超越。不排序的话，你会错误地让前方车辆去“追赶”后方车辆，完全颠倒了实际行驶逻辑。
• 以你给出的测试用例为例，原数组顺序是[0,4,2]，你先处理离target最远的车（position0），再处理最近的（position4），最后处理中间的（position2），这种顺序下，栈的弹出逻辑完全不符合实际追及场景，导致错误计算车队数量。

修复方案 #

核心思路 #

1. 按位置降序排序车辆：确保处理顺序是从离target最近的车到最远的车，这样我们可以依次判断后方车辆是否能追上前方已形成的车队。
2. 修正栈的判断逻辑：对于当前车辆的到达时间，如果它大于栈顶的时间，说明它无法追上前面的车队，会形成新的车队；否则，它会在到达终点前追上前面的车队，合并为一个，无需入栈。

修复后的代码 #

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    # 配对位置与速度，按位置从大到小排序（离目标近的先处理）
    cars = sorted(zip(position, speed), key=lambda x: -x[0])
    stack = []
    for pos, spd in cars:
        time = (target - pos) / spd
        # 当前车无法追上前面的车队，新增一个车队
        if not stack or time > stack[-1]:
            stack.append(time)
    return len(stack)

测试用例验证 #

针对你给出的测试用例target=10、position=[0,4,2]、speed=[2,1,3]：

• 排序后的车辆顺序为[(4,1), (2,3), (0,2)]，对应到达时间分别为6、≈2.666、5。
• 处理时，6先入栈；2.666小于6，说明会追上前方车队，不入栈；5小于6，同理不入栈。最终栈长度为1，符合预期结果。

内容的提问来源于stack exchange，提问作者Vasco Rodrigues Ribeiro