Leetcode1094. 拼车

Every day a Leetcode

题目来源： 1094. 拼车

解法1：差分数组

对于本题，设 a[i] 表示车行驶到位置 i 时车上的人数。我们需要判断是否所有 a[i] 都不超过 capacity。

trips[i] 相当于把 a 中下标从 from _i 到 to _i −1 的数都增加 numPassengers _i 。这正好可以用上面讲的差分数组解决。

代码：

/*
 * @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(to _i )。

空间复杂度：O(U)，U=max(to _i )。