LeetCode 1094 Car Pooling

Tag: 数组类题目 LeetCode Posted on 2022-02-12 17:08:27 Edited on 2022-02-12 17:21:47 Views: 156

概述

https://leetcode.com/problems/car-pooling/

暴力法

维护一个里程数组,里面记录对应该 km 的汽车容量,如果末段容量降到了负数,则拼车失败。

时间复杂度 O(mn),空间复杂度 O(n),其中 m 为拼车人数,n 为距离。

差分数组

显然我们应该对范围进行操作。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        int maxD = INT_MIN;
        int minD = INT_MAX;
        for (auto& t : trips) {
            diff[t[2]] += t[0];
            diff[t[1]] -= t[0];
            maxD = max(maxD, t[2]);
            minD = min(minD, t[1]);
        }
        int sum = 0;
        for (int i = maxD; i >= minD; i --) {
            int rest = capacity - diff[i] - sum;
            if (rest < 0) return false;
            sum += diff[i];
        }
        return true;
    }
};

有个可以优化的地方就是,实际上我们不需要遍历整个路段,只需要逆序遍历有人上下车的点即可。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        unordered_map<int, int> diff;
        set<int> s;
        for (auto& t : trips) {
            diff[t[2]] += t[0];
            diff[t[1]] -= t[0];
            s.insert(t[1]);
            s.insert(t[2]);
        }
        vector<int> points(s.begin(), s.end());
        sort(points.rbegin(), points.rend());
        int sum = 0;
        for (auto i : points) {
            int rest = capacity - diff[i] - sum;
            if (rest < 0) return false;
            sum += diff[i];
        }
        return true;
    }
};

不过由于需要给点进行排序,因此时间复杂度变成了 O(nlogn),尽管如此,当整个路段很稀疏时,我们的应该是要更快的。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/