拼车

• 一、题目描述
• 二、示例
• 三、难度
• 四、代码
• • Java版
  • • 差分数组法

一、题目描述

二、示例

三、难度

中等

四、代码

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));    }}