跳到主要内容

LeetCode 1109. 航班预订统计

本节目标

用差分数组把每笔闭区间预订压缩为两个端点更新。

这道题承接前缀信息与差分：每笔预订都会给一个连续航班区间加同一个人数。

查看原题

题意与约束​

bookings 的每项为 [first, last, seats]，表示从第 first 到第 last 个航班都增加 seats 个座位；返回每个航班的总预订数。

朴素思路及瓶颈​

逐笔预订遍历 [first, last]，给其中每个航班直接加上 seats，实现直观，但一段很长的区间会逐项更新。若有 m 笔预订和 n 个航班，最坏时间复杂度为 O(mn)；重复工作来自大量预订反复经过同一批位置，因此只记录区间开始与结束处的变化更合适。

端点记录变化​

对闭区间 [first, last]，在零基的 first - 1 处加 seats，在 last 处减 seats。若 last 已是最后一班，则不需要右端减法。最后从左到右累加差分，即得到每个航班的实际数量。

代码实现​

两份源码先记录所有区间的端点变化，再用一次前缀累加还原答案。

C++17
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> difference(n + 1, 0);
        for (const vector<int>& booking : bookings) {
            int first = booking[0] - 1;
            int last = booking[1];
            int seats = booking[2];
            difference[first] += seats;
            if (last < n) {
                difference[last] -= seats;
            }
        }

        vector<int> answer(n);
        int current = 0;
        for (int index = 0; index < n; index++) {
            current += difference[index];
            answer[index] = current;
        }
        return answer;
    }
};

复杂度分析​

设有 m 笔预订、n 个航班，时间复杂度为 O(m + n)，空间复杂度为 O(n)。

易错点​

  • 把航班编号直接当作零基下标，漏做 first - 1 转换。
  • 在 last == n 时访问差分数组之外的位置。

模式迁移​

多次区间加值、最后统一询问每个位置时，优先使用差分；若每次更新后都要马上查询，则需要更适合在线维护的数据结构。