【每日一题】拼车+【差分数组】

文章目录

Tag
题目来源
解题思路
- 方法一：差分
写在最后

Tag

【差分数组】【数组】【2023-12-02】

题目来源

1094. 拼车

解题思路

本题朴素的解题思路是统计题目中提到的每一个站点的车上人数，如果某个站点的车上人数大于车上的座位数直接返回 false，如果直到行程结束都没有返回 false，则直接返回 true。朴素方法的时间复杂度为 $O(n^2)$ ， $n$ 最大为 1000，该方法时间复杂度较高但是可以通过本题。

接下来将会介绍一种时间复杂度较优的方法，时间复杂度为 $O (n + U)$ 。

方法一：差分

我们先来看一下，朴素方法的实现代码：

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> peoples(10010);
        for (auto trip : trips) {
            for (int i = trip[1]; i < trip[2]; ++i) {
                peoples[i] += trip[0];
                if (peoples[i] > capacity) {
                    return false;
                }
            }
        }
        return true;
    }
};

注意观察朴素解法中对于数组 peoples 的更新，我们枚举并更新所有站点的车上人数，朴素方法的时间复杂度较高的原因就是此处的嵌套枚举更新人数。此处可以使用【差分数组】来优化时间复杂度。

什么是差分数组？

差分数组是一个与原数组长度相同的数组，其中，除了首元素，其余的每个元素都是原数组中相邻两个元素的差值。比如数组 arr = [1, 4, 5, 6] 的差分数组 diff = [1, 3, 1, 1]，数组 arr[i] = diff[0, ..., i]，即原数组 arr 中的第 i 个元素等于差分数组 diff 第 0 到第 i 个元素之和。

时间是如何优化的？

对于某一段旅行有 numPassengers 乘客，乘客上车点为 from，下车点为 to，这一段旅程的我们只需要更新差分数数组的两个位置对应的值，即更新乘客上车点 diff[from] += numPaaengers, 更新乘客下车点 diff[to] -= numPaaengers。此时的时间复杂度为 $\times n) = O(n)$ ， $n$ 为数组 trips 的长度。

然后，利用差分数组累加得到每个站点的车上人数，并与 capacity 比较，… 此处的时间复杂度为 $O (U)$ ， $U = max(to_i)$ 。

我们借助差分数组将嵌套枚举转化为了两个线性枚举，大大降低了时间复杂度。

实现代码

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int d[1001];
        memset(d, 0, sizeof(d));
        for (auto trip : trips) {
            int num = trip[0], from = trip[1], to = trip[2];
            d[from] += num;
            d[to] -= num;
        }

        int s = 0;
        for (int v : d) {
            s += v;
            if (s > capacity) {
                return false;
            }
        }
        return true;
    }
};