LeetCode 1094. 拼车

约 5 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 阿里
标签
数组 排序 堆（优先队列） 前缀和 模拟

题目描述

✅ 1094. 拼车

image-20260928225710349

image-20260928225710350

题意分析

每条行程给出一组乘客的人数、上车位置和下车位置。车辆只能沿同一方向前进，所有行程都需要执行，判断是否能在任何路段都不超过车辆容量。

乘客从上车位置开始占座，到达下车位置后即可离开。若有人在同一位置下车、另一些人上车，空出的座位可以立即使用，不要求两批人同时留在车内。行程在输入中不必按位置排序，判断的是沿路线前进时的真实乘坐人数。

解法：差分数组

核心思路

[!blue]

一组乘客只在位置区间 [from, to) 内占座：到 from 增加人数，到 to 人数减少。与其把区间内每个位置都加一遍，不如只记录人数发生变化的两个端点，这就是差分数组。

用 diff[x] 保存位置 x 上全部上下客的净人数变化。每条行程执行 diff[from] += passengers、diff[to] -= passengers，同一位置的多条变化要累加，不能互相覆盖。

随后按位置递增累加差分。处理完 diff[x] 后，current 等于在位置 x 完成上下客、驶向后续路段时的乘客数。一个行程在上车后持续对前缀和贡献人数，到下车位置再被负变化抵消，正好还原了它的整个占座区间。

同站上下客汇总成净变化，是因为可以先下车再上车：到站前的人数已在上一段检查，下车只会减少占用，全部上车后的最终人数也不超容量，就不存在中间超载。任意位置发现 current > capacity 即无解；恰好坐满仍然合法。

代码用最大下车位置决定差分长度，并多分配一项包含该位置。题目站点范围较小，直接扫描整个位置范围就能完成，不需要排序所有行程。

解题步骤

  1. 遍历行程找到最大下车位置 last，创建长度为 last + 1 的差分数组。
  2. 对每条行程，在上车位置累加乘客数，在下车位置减去同样人数。
  3. 从位置零开始依次累加 diff，得到当前路段的实际占座人数。
  4. 任意位置超过容量时返回 false；扫描结束都未超载则返回 true。

代码实现

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int last = 0;

        for (int[] trip : trips) {
            last = Math.max(last, trip[2]);
        }

        int[] diff = new int[last + 1];

        for (int[] trip : trips) {
            int passengers = trip[0];
            int from = trip[1];
            int to = trip[2];

            // 半开区间从上车站开始增加，在下车站恢复。
            diff[from] += passengers;
            diff[to] -= passengers;
        }

        int current = 0;

        for (int change : diff) {
            // 累加该站净变化后，得到上下客完成后的车内人数。
            current += change;

            if (current > capacity) {
                return false;
            }
        }

        return true;
    }
}

func carPooling(trips [][]int, capacity int) bool {
    last := 0
    for _, trip := range trips {
        if trip[2] > last {
            last = trip[2]
        }
    }

    diff := make([]int, last+1)
    for _, trip := range trips {
        passengers := trip[0]
        from := trip[1]
        to := trip[2]
        // 半开区间从上车站开始增加，在下车站恢复。
        diff[from] += passengers
        diff[to] -= passengers
    }

    current := 0
    for _, change := range diff {
        // 累加该站净变化后，得到上下客完成后的车内人数。
        current += change
        if current > capacity {
            return false
        }
    }

    return true
}

复杂度分析

  • 时间复杂度：O(N + U + 1)，N 为行程数，U 为最远下车位置。两次遍历行程后，再扫描全部站点位置。
  • 空间复杂度：O(U + 1)，用于差分数组，其他变量为常数空间。

关键点总结

[!green]

  • 半开区间明确下车位置不再占座，差分负变化应写在 to。
  • 端点变化的前缀和就是途中人数，不必逐条遍历整段乘车区间。
  • 同站事件允许先下后上，检查净变化后的人数即可。
  • 容量约束必须沿途检查，全部行程结束后的零人数不能代表途中安全。

易错点总结

[!yellow]

  • 在 to + 1 才减去人数：会让已经下车的人多占一段路，误判同站换乘。
  • 用赋值写差分：同站可能存在多条行程，必须累加所有变化。
  • 把容量相等也判成超载：只有人数严格大于容量时失败。
  • 按输入行程顺序直接累加人数：输入顺序不是车行顺序，应按位置处理变化。
  • 只检查最终总人数：乘客最终都会下车，中途是否超载需要在每个位置还原后检查。

相似题目

题目 难度 关联与区别
1109. 航班预订统计 中等 同样用差分累计区间载量，本题区间右端下车不再占用，需明确半开边界。
253. 会议室 II 中等 同样扫描起止事件求最大同时占用，原题每个会议权重1，本题每段行程权重是乘客数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/43357270
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！