Create 1094. 拼车.md

CompetitiveLin · CompetitiveLin · commit 80413e9b809e · 2024-01-02T10:33:01.000+08:00
diff --git a/Methodology/1094. 拼车.md b/Methodology/1094. 拼车.md
@@ -0,0 +1,61 @@
+#### 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
+```
+
+ **提示：** 
+
+*   `1 <= trips.length <= 1000`
+*   `trips[i].length == 3`
+*   `1 <= numPassengersi <= 100`
+*   `0 <= fromi < toi <= 1000`
+*   `1 <= capacity <= 10^5`
+
+---
+
+差分数组：
+
+初始化一个长度为 `1001` 的差分数组，遍历 `trips` 数组并确定最大长度，上车位置处增加 `numPassengers_i` ，下车位置处减少 `numPassengers_i`，再遍历一遍该差分数组，遍历的过程中如果数组和大于 `capacity`，证明超载，返回 `false`，否则遍历完成后返回` true`。
+
+```Java
+class Solution {
+    public boolean carPooling(int[][] trips, int capacity) {
+        int maxLength = 1001;
+        int[] arrays = new int[maxLength];
+        for(int i = 0; i < trips.length; i++){
+            arrays[trips[i][1]] += trips[i][0];
+            arrays[trips[i][2]] -= trips[i][0];
+            maxLength = Math.max(maxLength, trips[i][2]);
+        }
+        int count = 0;
+        for(int i = 0; i < maxLength; i++){
+            count += arrays[i];
+            if(count > capacity){
+                return false;
+            }
+        }
+        return true;
+    }
+}
+```
