苹果弃车

2月28号凌晨，著名外媒爆料：苹果公司放弃投入十多年的造车项目，将其中的大量资源转投至 AI 部门。

如此炸裂的事情，自然少不了世界级网红，特斯拉 CEO 埃隆·马斯克的点评：

敬礼+香烟？

有点 R.I.P. 的意思？

苹果的造车项目立项十年之久，耗费资金保守估计有近百亿美元。

但其实造车项目到了现在，胎死腹中，及时放弃才是最能理解的结局。

苹果最擅长的事情，是为未知领域指明方向，然后以领导者姿态来占领市场。

苹果立项造车的时候，看到了能源替代的大趋势和必然性，也看到了电动车可能作为特有计算平台的机会。

但可能是错估了造车所需要的资源，又或者根本苹果对此项目也是摇摆不定，导致十年过去了，第一款车还没投产。

我估计更加令苹果意想不到，也是让苹果决定放弃的造车的主要原因是：现如今的电动车领域已经不需要苹果来指明方向，以特斯拉为首的车企早就走出一条成熟道路，而且这条道路已经开始走后半程。

Vision Pro 或许能接过 iPhone 和 iPad 的棒，让苹果成为指明 AR/VR 领域发展方向的先行者，但电动车肯定不是。

苹果作为以轻资产赚大钱的世界代表。放弃造车，及时止损，投身 AI，才是正确的选择。

不要因为 OpenAI 的锋芒，不要因为放不下"天生骄傲"的状态，而选择不在人工智能领域上发力，否则很快就会冒出大量敢于以下犯上的科技企业。

...

回归主线。

做一道和「车」相关的题目。

题目描述

平台：LeetCode

题号：1094

车上最初有 capacity 个空座位，车只能向一个方向行驶（不允许掉头或改变方向）。

给定整数 capacity 和一个数组 trips, trip[i]=[numPassengersi,fromi,toi]表示第 i 次旅行有 numPassengersi乘客，接他们和放他们的位置分别是 fromi 和toi 。

这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5输出：true

提示：

差分

从朴素的想法开始：创建一个数组 cnt，用于存储从某个站点出发时，车上的乘客数量。

例如 cnt[x]=c 含义为在站点 x出发时（在该站点的下车和上车均完成），车上乘客数为 c个。

对于每个 trips[i]=(c,a,b)，我们需要对 [a,b)范围内的 cnt[j]进行加 ccc 操作。

处理完 trips 后，检查所有站点的乘客人数，根据是否满足 capacity 限制返回答案。

因此，这是一个关于「区间修改，单点查询」的经典问题，可使用「差分」求解。

所谓“差分”，是指 原数组中每个元素与前一元素之差所形成的数组，与之相对应的是“前缀和”。

我们知道，对原数组进行诸位累加（前缀计算操作），所得到的数组为前缀和数组。差分数组，则是对其执行前缀计算后，能够得到原数组的那个数组 。

关于「差分数组 - 原数组 - 前缀和数组」三者关系如图所示：

前缀和数组的主要作用，是利用「容斥原理」快速求解某段之和。例如要查询原数组 nums 中下标范围 [l,r]的和，可通过 sum[r]−sum[l−1]快速求解。

差分数组的主要作用，是帮助快速修改某段区间。

由于差分数组执行「前缀计算」后得到的是原数组，因此在差分数组上修改某个值，会对原数组某段后缀产生相同的影响。

因此，当我们想要对原数组的 [l,r] 进行整体修改时，只需要对差分数组的 l 和 r+1 位置执行相应操作即可。

举个 ，假设想对原数组 nums 的 [l,r] 进行整体“加一”操作，那么可转换为对差分数组 c[l] 的加一操作（等价对原数组的 [l,n−1]进行加一），以及对差分数组 c[r + 1] 的减一操作（等价于对原数组的 [r+1,n−1] 进行减一，最终只有 [l,r]有加一效果）。

至此，我们完成了对「差分」的基本学习：将原数组的区间修改等价为差分数组的特定位置修改。

回到本题，起始先用 nums 来作为差分数组，对于 trips[i]=(c,a,b)，有 ccc 个乘客在 aaa 点上车，在 bbb 点下车，因此对 [a,b) 进行整体加 ccc 操作，对应差分数组操作 nums[a] += c; nums[b] -= c。

处理完 trips 后，对差分数组 nums 进行前缀计算（可直接复用 nums，进行原地计算），便可得到各个站点的乘客数量，与 capacity 比较得出答案。

一些细节：为了方便，人为规定站点编号从 111 开始。

Java 代码：

class Solution { public boolean carPooling(int[][] trips, int capacity) { int[] nums = new int[1010]; for (int[] t : trips) { int c = t[0], a = t[1], b = t[2]; nums[a + 1] += c; nums[b + 1] -= c; } for (int i = 1; i <= 1000; i++) { nums[i] += nums[i - 1]; if (nums[i] > capacity) return false; } return true; }}

C++ 代码：

class Solution {public: bool carPooling(vector<vector<int>>& trips, int capacity) { vector<int> nums(1010, 0); for (const auto& t : trips) { int c = t[0], a = t[1], b = t[2]; nums[a + 1] += c; nums[b + 1] -= c; } for (int i = 1; i <= 1000; i++) { nums[i] += nums[i - 1]; if (nums[i] > capacity) return false; } return true; }};

Python 代码：

class Solution: def carPooling(self, trips: List[List[int]], capacity: int) -> bool: nums = [0] * 1010 for t in trips: c, a, b = t[0], t[1], t[2] nums[a + 1] += c nums[b + 1] -= c for i in range(1, 1001): nums[i] += nums[i - 1] if nums[i] > capacity: return False return True

TypeScript 代码：

function carPooling(trips: number[][], capacity: number): boolean { const nums = new Array(1010).fill(0); for (const t of trips) { const c = t[0], a = t[1], b = t[2]; nums[a + 1] += c; nums[b + 1] -= c; } for (let i = 1; i <= 1000; i++) { nums[i] += nums[i - 1]; if (nums[i] > capacity) return false; } return true;};时间复杂度：O(n+m)，其中n为数组 trips 大小；m=1000为位置值域大小空间复杂度：O(m)