差分数组算法
详情
1094. 拼车
class Solution {public boolean carPooling(int[][] trips, int capacity) {TreeMap<Integer, Integer> diff = new TreeMap<>();for (int[] trip : trips) {int num = trip[0], from = trip[1], to = trip[2];diff.merge(from, num, Integer::sum);diff.merge(to, -num, Integer::sum);}int sum = 0;for (int v: diff.values()) {sum += v;if (sum > capacity) {return false;}}return true;}
}
1109. 航班预订统计
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] res = new int[n + 1]; // 离开在后一个离开for (int[] booking : bookings) {int first = booking[0], last = booking[1], seat = booking[2];res[first - 1] += seat;res[last] -= seat;}for (int i = 1; i < n; i++) {res[i] += res[i - 1];}int[] ans = new int[n];System.arraycopy(res, 0, ans, 0, n);return ans;}
}
121. 买卖股票的最佳时机
class Solution {public int maxProfit(int[] prices) {int res = 0;int minPrice = prices[0];for (int price : prices) {res = Math.max(res, price - minPrice); // 计算minPrice = Math.min(minPrice, price); // 维护左边出现的最小价格}return res;}
}
122. 买卖股票的最佳时机 II
class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[] diff = new int[n];diff[0] = prices[0];int res = 0;for (int i = 1; i < n; i++) {diff[i] = prices[i] - prices[i - 1];res += Math.max(diff[i], 0);}return res;}
}
253. 会议室II
给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...](si<ei)[[s_1,e_1],[s_2,e_2],...] (s_i < e_i)[[s1,e1],[s2,e2],...](si<ei)， 为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2示例 2:
输入: [[7,10],[2,4]]
输出: 1
public class Solution {int minMeetingRooms(int[][] intervals) {int n = 10001;int[] diff = new int[n];for (int[] interval : intervals) {int start = interval[0], end = interval[1];diff[start] += 1;diff[end] -= 1;}int res = 0;for (int i = 1; i < n; i++) {diff[i] = diff[i - 1] + diff[i];res = Math.max(res, diff[i]);}return res;}
}