Medium

题目描述

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

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 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

解题思路

这是一道经典的区间更新问题，可以使用差分数组的技巧高效解决。

方法一：暴力解法 最直观的方法是遍历每个预订记录，对应的区间范围内所有航班都加上相应的座位数。但时间复杂度为 O(m*n)，在数据量较大时会超时。

方法二：差分数组（推荐） 差分数组是处理区间更新问题的经典技巧。核心思想是：

  1. 创建一个差分数组 diff，初始值为 0
  2. 对于每个区间 [first, last] 的更新值 seats：
    • 在 diff[first-1] 位置加上 seats（注意数组索引从0开始）
    • 在 diff[last] 位置减去 seats（如果 last < n）
  3. 最后对差分数组求前缀和，得到最终结果

这样做的原理是：差分数组记录了相邻元素之间的差值变化。当我们在位置 i 加上某个值，在位置 j+1 减去这个值时，前缀和计算后，区间 [i, j] 内的所有元素都会增加这个值。

时间复杂度降低到 O(m + n)，其中 m 是预订记录数，n 是航班数。

代码实现

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        
        for (auto& booking : bookings) {
            int first = booking[0] - 1;  // 转为0索引
            int last = booking[1] - 1;   // 转为0索引
            int seats = booking[2];
            
            diff[first] += seats;
            if (last + 1 < n) {
                diff[last + 1] -= seats;
            }
        }
        
        // 计算前缀和
        for (int i = 1; i < n; i++) {
            diff[i] += diff[i - 1];
        }
        
        return diff;
    }
};

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        
        for first, last, seats in bookings:
            diff[first - 1] += seats  # 转为0索引
            if last < n:
                diff[last] -= seats
        
        # 计算前缀和
        for i in range(1, n):
            diff[i] += diff[i - 1]
        
        return diff

public class Solution {
    public int[] CorpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        
        foreach (int[] booking in bookings) {
            int first = booking[0] - 1;  // 转为0索引
            int last = booking[1] - 1;   // 转为0索引
            int seats = booking[2];
            
            diff[first] += seats;
            if (last + 1 < n) {
                diff[last + 1] -= seats;
            }
        }
        
        // 计算前缀和
        for (int i = 1; i < n; i++) {
            diff[i] += diff[i - 1];
        }
        
        return diff;
    }
}

var corpFlightBookings = function(bookings, n) {
    const diff = new Array(n).fill(0);
    
    for (const [first, last, seats] of bookings) {
        diff[first - 1] += seats;  // 转为0索引
        if (last < n) {
            diff[last] -= seats;
        }
    }
    
    // 计算前缀和
    for (let i = 1; i < n; i++) {
        diff[i] += diff[i - 1];
    }
    
    return diff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型差分数组解法
时间复杂度O(m + n)
空间复杂度O(n)

其中 m 是预订记录数 bookings.length，n 是航班数。

相关题目