侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【差分数组】航班预订统计

GabrielxD
2022-10-11 / 0 评论 / 0 点赞 / 20 阅读 / 377 字 / 正在检测是否收录...

题目

1109. 航班预订统计


这里有 n 个航班,它们分别从 1n 进行编号。

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti包含 firstilasti )的 每个航班 上预订了 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 <= n <= 2 * 10^4
  • 1 <= bookings.length <= 2 * 10^4
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 10^4

解题

方法一:差分数组

思路

差分数组,注意要把序号减一才是下标。

代码

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diffs = new int[n + 1];
        for (int[] booking : bookings) {
            diffs[booking[0] - 1] += booking[2];
            diffs[booking[1]] -= booking[2];
        }
        int[] ans = new int[n];
        for (int i = 0, diff = 0; i < n; ++i) ans[i] = diff += diffs[i];
        return ans;
    }
}
0

评论区