Recap: 差分数组
1.想一个场景, 需要频繁地给数组的某些不同的区间频繁的增加或者减少, 例给给定一个数组 nums, 然后给 nums[2..6] 都 +1, 然后对 nums[3..0]都 -3, 然后对 nums[0..4] 都+2, 朴素的想法是仍然是多次 O(n) 扫描
2.想一下这里有没有优化的空间
3.差分数组的使用场景是频繁地对数组的某个区间进行元素进行增减, 构造差分数组 diff[i] = nums[i] - nums[i-1]
原始数组 nums = [8,2,6,3,1]
差分数组 diff = [8,-6,4,-3,2]
4.利用差分数组也可以构造出来原始数组, 对于 nums[i] = diff[i] + nums[i-1]
// 构造差分数组
diff[0] = nums[0]
diff[1] = nums[1] - nums[0]
diff[2] = nums[2] - nums[1]
// 还原数组
nums[0] = diff[0]
nums[1] = diff[1] + nums[0] = diff[1] + diff[2]
nums[2] = diff[2] + nums[1] = diff[2] + diff[1] + diff[0]
vector<int> res(n);
res[0] = diff[0];
for (int i = 1; i < diff.size(); ++i) {
res[i] = res[i-1] + diff[i];
}
5.有了差分数组, 如何实现数组区间增减? 如果我们相对 nums[i..j] 区间全部+3, 我们需要 diff[i] += 3, 然后 diff[j+1] -= 3, 然后重新操作还原数组过程, 想一下怎么实现的, 假设我们对原始的数组 index[1..3] 都 +3
原始数组 nums [8,2,6,3,1]
差分数组 diff [8,-6,4,-3,2]
更新后的原始数组nums [8,5,9,6,1] 对原始的数组 index[1..3] 都 +3
更新后的差分数组diff [8,-3,4,-3,-5] 和原始差分数组的区别在于 diff[i] += 3 && diff[j+1] -= 3
思考差分数组 diff[i] += 3 达到了什么效果, 相当于对 nums[i..] 后面的所有元素都+3, 换句话说, 对当前的元素比前一个元素增加了 3, 那么后面的元素仍然比前一个元素大 diff[i+1], diff[i+2], 这个值都被被动的加上了3
同理 diff[j+1] -= 3, 对从 nums[j+1..] 后面的元素所有都-3, 进行 +3 和 -3 操作之后都没有变
因此, 当我们相对 nums[i..j] 都进行+x的操作, 只需要对 diff[i]+=x, 且对 diff[j+3]-=x, 然后利用差分数组对原始的操作进行还原操作
1109.航班预定统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。示例 1： 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]
分析:
1.座位数就是区间内的和, 用差分数组辅助统计
class Solution {
private:
vector<int> nums;
vector<int> diff;
public:
void buildDiff() {
diff[0] = nums[0];
for (int i = 1; i < nums.size(); ++i) {
diff[i] = nums[i] - nums[i-1];
}
return;
}
vector<int> recoverNums() {
vector<int> res(nums.size());
res[0] = diff[0];
for (int i = 1; i < diff.size(); ++i) {
res[i] = res[i-1] + diff[i];
}
return res;
}
void increment(int l, int r, int val) {
diff[l] += val;
if (r+1 < diff.size()) {
diff[r+1] -= val;
}
return;
}
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
nums.resize(n, 0);
diff.resize(n);
buildDiff();
for (int i = 0; i < bookings.size(); ++i) {
int l = bookings[i][0]-1;
int r = bookings[i][1]-1;
int v = bookings[i][2];
increment(l, r, v);
}
return recoverNums();
}
};
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.题目提示有 1000 个车站, 判断容量其实是对各种区间内做加法, 我们对于每一个 fromi 到 ti 进行增减, 上车区间是 trip[i][1], 下车区间是 trip[i][2]-1, 对这个区间进行增减
2.最后依次判断每个区间都是满足 capacity 的
class Solution {
private:
vector<int> nums;
vector<int> diff;
public:
void buildDiff() {
diff[0] = nums[0];
for (int i = 1; i < nums.size(); ++i) {
diff[i] = nums[i] - nums[i-1];
}
}
void increment(int i, int j, int val) {
diff[i] += val;
if (j+1 < diff.size()) {
diff[j+1] -= val;
}
}
vector<int> recover() {
vector<int> ret(nums.size());
ret[0] = diff[0];
for (int i = 1; i < diff.size(); ++i) {
ret[i] = ret[i-1] + diff[i];
}
return ret;
}
bool carPooling(vector<vector<int>>& trips, int capacity) {
nums.resize(1000+1, 0);
diff.resize(1000+1);
for (vector<int> trip : trips) {
int i = trip[1];
int j = trip[2]-1;
int val = trip[0];
increment(i, j, val);
}
vector<int> ret = recover();
int max = *max_element(ret.begin(), ret.end());
return max <= capacity;
}
};
253.会议室 II
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
示例 1：输入：intervals = [[0,30],[5,10],[15,20]] 输出：2
示例 2：输入：intervals = [[7,10],[2,4]] 输出：1 提示：
分析:
1.最小的会议室数量就是最大的重叠区间数量; 我们用扫描线的方法, 首先将所有区间的左侧节点和右侧节点分别放在两个数组里面, 然后对这两个数组进行排序
2.用双指针同时遍历两个数组, 如果遇到首节点那么+1, 遇到尾节点那么-1; 在这个过程中更新最大的重叠区间个数
3.如何模拟这种扫描的过程呢, 要用到双指针, 当前指针设置为扫描线, 它比较的是begins[i] < ends[j], 如果是那么就另扫描线移动
4.相似题目: 732
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
if (n <= 0) {
return 0;
}
vector<int> begins;
vector<int> ends;
for (auto& inter : intervals) {
begins.emplace_back(inter[0]);
ends.emplace_back(inter[1]);
}
sort(begins.begin(), begins.end());
sort(ends.begin(), ends.end());
int res = 0;
int count = 0;
int i = 0;
int j = 0;
while (i < n && j < n) {
if (begins[i] < ends[j]) {
++count;
++i;
} else {
--count;
++j;
}
res = max(res, count);
}
return res;
}
};
转载请注明来源, from goldandrabbit.github.io
