LC 1094. 拼车
题目描述
这是 LeetCode 上的 1094. 拼车 ,难度为 中等。
车上最初有 capacity
个空座位,车只能向一个方向行驶(不允许掉头或改变方向)。
给定整数 capacity
和一个数组 trips
, $trip[i] = [numPassengers{i}, from{i}, to{i}]$ 表示第 i
次旅行有 $numPassengers{i}$ 乘客,接他们和放他们的位置分别是 $from{i}$ 和 $to{i}$ 。
这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时,返回 true
,否则请返回 false
。
示例 1:1
2
3输入:trips = [[2,1,5],[3,3,7]], capacity = 4
输出:false
示例 2:1
2
3输入:trips = [[2,1,5],[3,3,7]], capacity = 5
输出:true
提示:
- $1 <= trips.length <= 1000$
- $trips[i].length = 3$
- $1 <= numPassengers_{i} <= 100$
- $0 <= from{i} < to{i} <= 1000$
- $1 <= capacity <= 10^5$
差分
从朴素的想法开始:创建一个数组 cnt
,用于存储从某个站点出发时,车上的乘客数量。
例如 $cnt[x] = c$ 含义为在站点 $x$ 出发时(在该站点的下车和上车均完成),车上乘客数为 $c$ 个。
对于每个 $trips[i] = (c, a, b)$,我们需要对 $[a, b)$ 范围内的 $cnt[j]$ 进行加 $c$ 操作。
处理完 trips
后,检查所有站点的乘客人数,根据是否满足 capacity
限制返回答案。
因此,这是一个关于「区间修改,单点查询」的经典问题,可使用「差分」求解。
所谓“差分”,是指 原数组中每个元素与前一元素之差所形成的数组,与之相对应的是“前缀和”。
我们知道,对原数组进行诸位累加(前缀计算操作),所得到的数组为前缀和数组。差分数组,则是对其执行前缀计算后,能够得到原数组的那个数组 🤣 。
关于「差分数组 - 原数组 - 前缀和数组」三者关系如图所示:
前缀和数组的主要作用,是利用「容斥原理」快速求解某段之和。例如要查询原数组 nums
中下标范围 $[l, r]$ 的和,可通过 $sum[r] - sum[l - 1]$ 快速求解。
差分数组的主要作用,是帮助快速修改某段区间。
由于差分数组执行「前缀计算」后得到的是原数组,因此在差分数组上修改某个值,会对原数组某段后缀产生相同的影响。
因此,当我们想要对原数组的 $[l, r]$ 进行整体修改时,只需要对差分数组的 $l$ 和 $r + 1$ 位置执行相应操作即可。
举个 🌰,假设想对原数组 nums
的 $[l, r]$ 进行整体“加一”操作,那么可转换为对差分数组 c[l]
的加一操作(等价对原数组的 $[l, n - 1]$ 进行加一),以及对差分数组 c[r + 1]
的减一操作(等价于对原数组的 $[r + 1, n - 1]$ 进行减一,最终只有 $[l, r]$ 有加一效果)。
至此,我们完成了对「差分」的基本学习:将原数组的区间修改等价为差分数组的特定位置修改。
回到本题,起始先用 nums
来作为差分数组,对于 $trips[i] = (c, a, b)$,有 $c$ 个乘客在 $a$ 点上车,在 $b$ 点下车,因此对 $[a, b)$ 进行整体加 $c$ 操作,对应差分数组操作 nums[a] += c; nums[b] -= c
。
处理完 trips
后,对差分数组 nums
进行前缀计算(可直接复用 nums
,进行原地计算),便可得到各个站点的乘客数量,与 capacity
比较得出答案。
一些细节:为了方便,人为规定站点编号从 $1$ 开始。
Java 代码:
1 |
|
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> nums(1010, 0);
for (const auto& t : trips) {
int c = t[0], a = t[1], b = t[2];
nums[a + 1] += c; nums[b + 1] -= c;
}
for (int i = 1; i <= 1000; i++) {
nums[i] += nums[i - 1];
if (nums[i] > capacity) return false;
}
return true;
}
};
Python 代码:1
2
3
4
5
6
7
8
9
10
11class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
nums = [0] * 1010
for t in trips:
c, a, b = t[0], t[1], t[2]
nums[a + 1] += c
nums[b + 1] -= c
for i in range(1, 1001):
nums[i] += nums[i - 1]
if nums[i] > capacity: return False
return True
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12function carPooling(trips: number[][], capacity: number): boolean {
const nums = new Array(1010).fill(0);
for (const t of trips) {
const c = t[0], a = t[1], b = t[2];
nums[a + 1] += c; nums[b + 1] -= c;
}
for (let i = 1; i <= 1000; i++) {
nums[i] += nums[i - 1];
if (nums[i] > capacity) return false;
}
return true;
};
- 时间复杂度:$O(n + m)$,其中 $n$ 为数组
trips
大小;$m = 1000$ 为位置值域大小 - 空间复杂度:$O(m)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1094
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!