LeetCode 1109. 航班预订统计

Categories:

题目描述
思路分析
1. 解法一：差分数组（推荐）
相似题目

题目描述

✅ 1109. 航班预订统计

思路分析

解法一：差分数组（推荐）

核心思路：

对区间 [l, r] 增加 val 可用差分数组 diff 处理。

执行 diff[l] += val、diff[r+1] -= val。

最终对 diff 做前缀和得到每个航班的订座数。

复杂度分析：

时间复杂度：O(n + m)，其中 n 为航班数，m 为预订数。

空间复杂度：O(n)，差分数组占用线性空间。

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];

        // 区间增量更新
        for (int[] b : bookings) {
            int l = b[0] - 1;
            int r = b[1] - 1;
            int val = b[2];
            diff[l] += val;
            if (r + 1 < n) {
                diff[r + 1] -= val;
            }
        }

        int[] res = new int[n];
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            res[i] = cur;
        }

        return res;
    }
}

func corpFlightBookings(bookings [][]int, n int) []int {
	diff := make([]int, n+1)

	// 区间增量更新
	for _, b := range bookings {
		l := b[0] - 1
		r := b[1] - 1
		val := b[2]
		diff[l] += val
		if r+1 < n {
			diff[r+1] -= val
		}
	}

	res := make([]int, n)
	cur := 0
	for i := 0; i < n; i++ {
		cur += diff[i]
		res[i] = cur
	}

	return res
}

相似题目

题目	难度	考察点
370. 区间加法	中等	差分数组
1094. 拼车	中等	差分
1109. 航班预订统计	中等	差分
1589. 所有排列中的最大和	中等	差分 + 贪心
1310. 子数组异或查询	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/30770185