LeetCode 1094. 拼车

Categories:

题目描述
思路分析
1. 解法一：差分数组（推荐）
相似题目

题目描述

✅ 1094. 拼车

思路分析

解法一：差分数组（推荐）

核心思路：

记录每个站点上下车的人数变化。

前缀累加即可得到任一站点的实时载客量。

若载客量超过容量则返回 false。

复杂度分析：

时间复杂度：O(n + M)，其中 n 表示行程数，M 为最大站点编号。

空间复杂度：O(M)，用于差分数组。

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int max = 0;
        for (int[] trip : trips) {
            max = Math.max(max, trip[2]);
        }

        int[] diff = new int[max + 1];
        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            if (trip[2] < diff.length) {
                diff[trip[2]] -= trip[0];
            }
        }

        int curr = 0;
        for (int i = 0; i <= max; i++) {
            curr += diff[i];
            if (curr > capacity) {
                return false;
            }
        }

        return true;
    }
}

func carPooling(trips [][]int, capacity int) bool {
	maxStop := 0
	for _, trip := range trips {
		if trip[2] > maxStop {
			maxStop = trip[2]
		}
	}

	diff := make([]int, maxStop+1)
	for _, trip := range trips {
		diff[trip[1]] += trip[0]
		if trip[2] < len(diff) {
			diff[trip[2]] -= trip[0]
		}
	}

	curr := 0
	for i := 0; i <= maxStop; i++ {
		curr += diff[i]
		if curr > capacity {
			return false
		}
	}

	return true
}

相似题目

题目	难度	考察点
1109. 航班预订统计	中等	差分数组
370. 区间加法	中等	差分数组
1589. 所有排列中的最大和	中等	差分数组
56. 合并区间	中等	区间处理
1094. 拼车	中等	差分数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/43357270