LeetCode 1094. 拼车

2025-05-06 HGNULB 约 9 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 1094. 拼车

题意分析

车只能向前开，给定若干条行程，每条包含乘客数、上车点和下车点，以及车的载客上限，判断是否存在一种可行的接送安排——其实没有选择余地，所有行程都必须接，问的是「全接下来会不会超载」。

关键是理解一位乘客占用座位的时间跨度：他从 from 上车、在 to 下车，所以占据的是半开区间 [from, to)。到达 to 这个站点的瞬间他已经下车，让位给同站上车的人，这个开闭区间的细节直接决定答案。

约束里站点编号有明确上界（不超过 1000），行程数量也只有上千条。站点上界是一条强信号：它允许我们开一个以站点为下标的数组，把「区间操作」摊平到坐标轴上，而不必对行程排序或用堆去模拟时间推进。

边界包括：行程为空时直接可行；某条行程本身乘客数就超过 capacity 时必须返回 false；多条行程在同一站点同时上车，人数要累加而不是取最大。

解法：差分数组

核心思路

最直接的模拟是：开一个长度为站点数的数组，对每条行程把 [from, to) 区间里的每个位置都加上乘客数，最后扫一遍看有没有超过 capacity。这是对的，但每条行程要做 $O(U)$ 次单点加，总代价是 $O(n \cdot U)$，区间长时会做大量重复加法。

瓶颈在于「区间内每个位置都要动」。观察到我们最终关心的只是各位置的人数，而人数只在「有人上车」或「有人下车」的站点才发生变化，中间的站点人数恒定不变。也就是说，真正携带信息的是变化量，而不是每个位置的绝对值。

于是改为记录变化：开数组 diff，对每条行程只做两次单点操作——diff[from] += passengers 表示这里上来这么多人，diff[to] -= passengers 表示这里下去这么多人。区间加就此从 $O(U)$ 降到 $O(1)$。

由此得到扫描阶段的不变量：从左到右累加 diff 时，current 恒等于车辆刚驶过位置 i 后车上的实际人数，因为它等于所有满足 from <= i 的行程的上车人数减去所有满足 to <= i 的行程的下车人数，正是「已上车但还没下车」的人的总和。

有了这条不变量，判定就变得非常直接：只要某个位置上 current 超过 capacity，说明这一刻车上人数超限，直接返回 false；扫完全程都没超，说明每一刻都合法，返回 true。注意 diff[to] -= passengers 里用的是 to 而不是 to + 1，正对应半开区间，也正对应「同站先下后上」的现实语义。

解题步骤

先扫一遍所有行程求出最大的下车位置 last，用它决定 diff 数组的长度。以实际数据定长而不是硬编码站点上界，能避免题目改约束时失效，也省下无用空间。

创建长度为 last + 1 的 diff 数组。加一是为了让下标 last 本身可写：某条行程在最远端下车时要执行 diff[last] -= passengers，没有这一格就会越界。

遍历每条行程，做 diff[from] += passengers 和 diff[to] -= passengers 两次操作。用 += 而非赋值，是因为同一站点可能既有多条行程上车也有多条下车，变化量必须叠加。

从下标 0 开始累加 diff 得到 current，即当前位置的车上人数。每累加一次就检查一次，因为「超载」是对每一时刻的约束，只要有一刻违反整体就不可行。

一旦 current > capacity 立即返回 false，提前退出既省时间也让逻辑更清楚；扫描完整个数组都没触发，返回 true。

以 trips = [[2,1,5],[3,3,7]]、capacity = 4 走一遍。最大下车位置是 7，所以 diff 长度为 8，初始全 0。

处理第一条行程 [2,1,5]：diff[1] += 2、diff[5] -= 2，diff 变成 [0,2,0,0,0,-2,0,0]。处理第二条 [3,3,7]：diff[3] += 3、diff[7] -= 3，diff 变成 [0,2,0,3,0,-2,0,-3]。

开始累加。位置 0：current = 0，不超过 4。位置 1：current = 2，此时第一位乘客组已上车，未超。位置 2：current 仍是 2。位置 3：current = 2 + 3 = 5，超过 capacity = 4，立即返回 false。

结论正确：在站点 3 到站点 5 之间，前一组 2 人还没下车，后一组 3 人已经上车，车上同时有 5 人，超出 4 座上限。

再用 trips = [[2,1,5],[3,5,7]]、capacity = 3 验证半开区间的作用。diff 为 [0,2,0,0,0,1,0,-3]（位置 5 上 -2 与 +3 叠加成 +1）。累加得位置 1 到 4 是 2，位置 5 是 3，位置 6 是 3，位置 7 是 0，全程不超过 3，返回 true。若错误地写成 diff[to + 1] -= passengers，位置 5 的 current 会变成 5，误判为 false。

代码实现

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)$，n 是行程数、U 是最大下车站点。建差分时每条行程只做两次单点更新，扫描时每个站点只累加一次。

空间复杂度：$O(U)$，差分数组的长度由最远站点决定，与行程数无关；本题 U 被约束在 1000 量级，因此实际上是常数级的额外空间。

关键点总结

「对区间整体加值、最后查询各点结果」这类离线批量操作，标准解法就是差分：把 $O(len)$ 的区间加变成两次单点改，再用一次前缀和还原。

差分与前缀和互为逆运算，写代码前先确认清楚区间是闭是开——闭区间 [l, r] 要写 diff[r+1] -= v，半开区间 [l, r) 要写 diff[r] -= v，写错就是经典的差一错误。

坐标范围有明确且不大的上界时，优先考虑按坐标开数组，比按事件排序更简单也更快；坐标范围极大或是浮点数时才需要退回排序或离散化。

判定类问题只要找到一个反例位置就能立刻返回，不必等扫描结束，提前退出让最坏情况不变、平均情况更快。

面试视角：面试官通常希望你从「暴力区间加」讲到「差分」，再主动对比另一条主流路线——把每条行程拆成 (from, +p) 和 (to, -p) 两个事件后排序扫描，复杂度 $O(n \log n)$ 但不依赖坐标范围。能说清「坐标有界选差分、坐标无界选事件排序」这条选择标准，比只会一种写法强得多。

易错点总结

错误写法：把下车写成 diff[to + 1] -= passengers 当成闭区间处理 → 用例 trips = [[2,1,5],[3,5,7]], capacity = 3，站点 5 的人数被算成 5，返回 false，正确答案是 true。

错误写法：差分数组长度只开 last 而不是 last + 1 → 用例 trips = [[2,1,5]]，执行 diff[5] -= 2 时下标等于长度，Java 抛越界异常、Go 直接 panic。

错误写法：区间更新用赋值 diff[from] = passengers → 用例 trips = [[2,1,5],[3,1,7]], capacity = 4，站点 1 的两组乘客后者覆盖前者，人数被算成 3，返回 true，正确答案是 false。

错误写法：先累加完整个 diff 再统一判断最大值是否超限 → 逻辑本身没错但白白丢掉提前退出；若顺手写成「取 current 的最后一个值判断」则用例 trips = [[9,1,2]], capacity = 4 会因为终点人数归零而返回 true，正确答案是 false。

错误写法：判定写成 current >= capacity → 用例 trips = [[4,1,5]], capacity = 4，恰好坐满被判超载返回 false，正确答案是 true。

错误写法：把 trip 三个字段的顺序记成 [from, to, passengers] → 用例 trips = [[2,1,5]], capacity = 4，人数与站点互换，diff[2] += 1、diff[5] -= 1 完全算错，甚至可能因为站点值超出数组长度而越界。

错误写法：忘记求 last 而直接开固定长度 1001 的数组 → 本题能过，但一旦站点上界改成 $10^9$ 就立刻内存爆炸；更糟的是若硬编码成 1000，用例含 to = 1000 时 diff[1000] 恰好越界。

错误写法：排序后只两两检查相邻行程是否重叠超载 → 用例 trips = [[2,1,5],[3,3,7],[1,4,6]], capacity = 5，任意两条相加都不超过 5，但站点 4 处三组人同时在车上共 6 人，这种写法返回 true，正确答案是 false。

错误写法：用哈希表存 diff 却按插入顺序遍历 → 用例 trips = [[3,5,7],[2,1,5]], capacity = 4，累加顺序变成 5、7、1、5，current 的含义彻底失效，返回 true，正确答案是 false；差分还原必须严格按坐标升序。

错误写法：担心负数而给 current 加上 Math.max(current, 0) 的钳制 → 用例 trips = [[2,1,5],[3,5,7]], capacity = 3，正常的下车扣减被吞掉，站点 5 之后人数虚高，返回 false，正确答案是 true。

相似题目

题目	难度	考察点
370. 区间加法	中等	差分的裸题，最后要还原整个数组而不是做判定
1109. 航班预订统计	中等	闭区间语义，下标从 1 开始，`diff[r]` 的偏移与本题相反
252. 会议室	简单	容量退化为 1，排序后只需检查相邻会议是否重叠
253. 会议室 II	中等	求同时重叠的最大数量而非判定，坐标无界时要用堆或事件排序
732. 我的日程安排表 III	困难	在线动态插入区间，需要线段树或有序表维护实时最大重叠数
56. 合并区间	中等	输出合并后的区间集合，考察排序后的一次线性归并
1526. 形成目标数组的子数组最少增加次数	困难	反向使用差分，答案是相邻差值中正增量之和