题目大意：
拼车
假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。
这儿有一份行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：
・必须接送的乘客数量；
・乘客的上车地点；
・以及乘客的下车地点。
这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。
请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所用乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false
示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true
示例 3：
输入：trips = [[2,1,5],[3,5,7]], capacity = 3 输出：true
示例 4：
输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11 输出：true
提示：
你可以假设乘客会自觉遵守 “先下后上” 的良好素质
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1094
解题思路分析：
这道题的数据规模并不是很大，所以暴力解是可行的，核心判断依据为，当前站的载客总量是否大于capacity，大于的话直接返回false，小于的话继续检查下一站，直到结束，都符合不超载条件的话，返回true。
先看暴力解算法（优化方案在后），先建立一个数组sum，用于记录当前站的载客数，我们循环整个trips 数组，取得每个行程的起点和终点，然后在数组sum的该区间内加入该行程的人数。注意区间范围应该是大于等于起点到小于终点的范围（因为到终点位置时乘客已经下车）。这样时间复杂度为n的平方。
代码如下：
public boolean carPooling(int[][] trips, int capacity) {
int[] sum = new int[1001]; // 构建数组，为了判断每站的乘客数
for(int[] trip: trips){ // 循环trips
for(int i=trip[1];i<trip[2];i++){ // 循环每个trip的起点到终点
sum[i]+=trip[0]; // 在每一站加入当前trip的人数
if(sum[i] > capacity){ // 如果超载返回false
return false;
}
}
}
return true;
}此解运行时间为8ms。
Runtime: 8 ms, faster than 42.40% of Java online submissions for Car Pooling.
Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Car Pooling.
虽然暴力解的运行效率还算说得过去，而且Leetcode本身没有提供大数量级的测试数据，但我们应该考虑一下更优的解法。
优化暴力解的重点在于如何简化2层循环为1层循环（时间复杂度降为O(n)）。其实当循环trips时我们没有必要将当前trip的区间范围都操作一遍，我们只需要记录起点时上车的乘客变化以及终点时下车的乘客变化即可。上车时人数增加可记为正数，下车时人数减少记为负值，用这个值来更新sum数组，对应的人数相对变化情况，这样循环一遍 trips 过后，每站的人数变化就会一目了然，因为是人数的相对变化情况，所以求某一站当前的总人数应该是从 sum数组 的第0位累加到当前位置的总数。举个例子，比如第一站上了3个人，第二站上了1个人，下了2个人，第三站上了4个人，下了6个人。这时sum数组应该是{3, -1, -2}
这样，可以利用preSum的思路来计算出每站的乘客数，继而判断出是否超载。
代码如下：
public boolean carPooling(int[][] trips, int capacity) {
int[] sum = new int[1001]; // 记录每一站乘客的相对变化
for(int[] trip: trips){ // 循环trips
sum[trip[1]]+=trip[0]; // 起点增加此trip的人数
sum[trip[2]]-=trip[0]; // 终点减少此trip的人数
}
for(int i=0;i<sum.length;i++){ // 利用前缀和判断当前站的乘客数
sum[i] = i==0 ? sum[i] : sum[i]+sum[i-1];
if(sum[i] > capacity){
return false;
}
}
return true;
}此解法用时1ms。
Runtime: 1 ms, faster than 99.51% of Java online submissions for Car Pooling.
Memory Usage: 42.4 MB, less than 100.00% of Java online submissions for Car Pooling.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1094-car-pooling-解题思路分析/