JZX轻语：简

LeetCode 1109 - 航班预订统计

发表于2024年06月14日

#前缀和 #差分数组 #差分

今天做的第二道差分数组题，上一道是1094-拼车，本质做法和上一道是一样的，只不过这道题左右都是闭区间。最后通过累加就地恢复为原数组即可。

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        for first, last, seats in bookings:
            # 注意题目中的first, last是从1开始计数的
            # 而我们的结果数组从0开始计数
            # 因此需要-1
            diff[first - 1] += seats
            # 此时这里的从1计数的last其实可以看成（从0计数的）开区间了
            if last < n:
                diff[last] -= seats
        # 就地累加恢复数组
        ans = diff
        for i in range(len(ans)):
            ans[i] += ans[i - 1] if i > 0 else 0
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/corporate-flight-bookings/