1094. 拼车
拼车
一、题目描述
二、示例
三、难度
中等
四、代码
Java版
差分数组法
/** * @author Kidd * @create 2022-04-21 14:18 */public class Solution { private int[] diff; public boolean carPooling(int[][] trips, int capacity) { //最终的车站 int max = 0; for (int[] outer : trips) { if (max < outer[2]) max = outer[2]; } diff = new int[max + 1]; for (int[] outer : trips) { //乘客在车上[outer[1],outer[2]-1] 在outer[2]下车 diff[outer[1]] += outer[0]; //(outer[2]-1)+1 if(outer[2] < diff.length) diff[outer[2]] -= outer[0]; } //还原 int[] res = new int[diff.length]; res[0] = diff[0]; //结果数组中的元素都⼩于 capacity,就说明未超载 if (res[0] > capacity) return false; else for (int i = 1; i < diff.length; ++i) { res[i] = res[i - 1] + diff[i]; if (res[i] > capacity) return false; } return true; } public static void main(String[] args) { int capacity = 16;//空座位 int[][] updates = { {7, 5, 6}, {6, 7, 8}, {10, 1, 6} }; Solution s = new Solution(); System.out.print(s.carPooling(updates, capacity)); }}