题目描述
官方描述(中文)
2021/08/31每日一题
思路
这道题目用到了前缀和+差分数组。差分数组介绍, 对于一个预定区间预定的座位数是相同的,也就是对于原数组[i, j]区间同时加预定座位数,而这个条件完美的符合了差分数组的作用。
- 新建一个大小为n的数组A,数组内的数字都为0;
- 求数组A的差分数组B,显然A的差分数组就是A。为了方便区分将其命名为B,实际上B就是A。
- 对于区间[i,j],B[i-1]+=addNum, B[j]-=addNum.
- 最后对B求取前缀和数组,得到的就是统计列表
代码
class Solution
{
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n)
{
vector<int>res(n, 0);
for (const auto& iter : bookings)
{
if (iter.size() < 3)continue;
res[iter[0] - 1] += iter[2];
if (iter[1] < n)
{
res[iter[1]] -= iter[2];
}
}
for (auto i = 1; i < res.size(); ++i)
{
res[i] += res[i - 1];
}
return res;
}
};
运行结果
Q.E.D.