地址:
https://leetcode.cn/problems/car-pooling/description/
解法一:暴力解法
class Solution {public boolean carPooling(int[][] trips, int capacity) {//特殊条件判断if(null==trips||capacity<=0){return false;}int [] d = new int[1001];//暴力解法 直接记录每个时刻位置车上有多少个人 找出最大值是否小于capacityfor(int [] m : trips){int num = m[0],from =m[1],to=m[2];for(int i=from;i<to;i++){d[i]+=num;}}for(int x:d){if(x>capacity){return false;}}return true;}
}
解法二:差分数组
class Solution {public boolean carPooling(int[][] trips, int capacity) {int[] d = new int[1001];for (int[] t : trips) {int num = t[0], from = t[1], to = t[2];d[from] += num;d[to] -= num;}int s = 0;for (int v : d) {s += v;//根据差分数组的性质只要s>capacity就说明在这个位置上超员了if (s > capacity) {return false;}}return true;}
}