LC.P1094[拼车]

方法一：差分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] d = new int[1001];
        for (int[] trip : trips) {
            int num = trip[0], from = trip[1], to = trip[2];
            d[from] += num;
            d[to] -= num;
        }
        int sum = 0;
        for (int x : d) {
            sum += x;
            if (sum > capacity) return false;
        }
        return true;
    }
}
  • 时间复杂度：$O(n + U)$，其中$n$为$trips$的长度，$U = max(from_i)$
  • 空间复杂度：$O(U)$