Leetcode1094. 拼车
Every day a Leetcode
题目来源：1094. 拼车
解法1：差分数组
对于本题，设 a[i] 表示车行驶到位置 i 时车上的人数。我们需要判断是否所有 a[i] 都不超过 capacity。
trips[i] 相当于把 a 中下标从 fromi 到 toi−1 的数都增加 numPassengersi。这正好可以用上面讲的差分数组解决。
代码：
/*
* @lc app=leetcode.cn id=1094 lang=cpp
*
* [1094] 拼车
*/
// @lc code=start
class Solution
{
public:
bool carPooling(vector<vector<int>> &trips, int capacity)
{
vector<int> diff(1001, 0);
for (vector<int> &trip : trips)
{
int numPassengers = trip[0], from = trip[1], to = trip[2];
diff[from] += numPassengers;
diff[to] -= numPassengers;
}
int passengers = 0;
for (int &d : diff)
{
passengers += d;
if (passengers > capacity)
return false;
}
return true;
}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n+U)，其中 n 是数组 trips 的长度，U=max(toi)。
空间复杂度：O(U)，U=max(toi)。