📃 题目描述

题目链接：1109. 航班预订统计 (opens new window)

🔔 解题思路

换一种思路理解题意，将问题转换为：某公交车共有 n 站，第 i 条记录 bookings[i] = [i, j, k] 表示在 i 站上车 k 人，乘坐到 j 站，在 j+1 站下车，需要按照车站顺序返回每一站车上的人数

根据 1 的思路，定义 counter[] 数组记录每站的人数变化，counter[i] 表示第 i 站。遍历 bookings[]：bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i] += k，在 j+1 站减少 k 人即 counters[j + 1] -= k

遍历（整理）counter[] 数组，得到每站总人数： 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] gap = new int[n + 2];
        gap[0] = 0;

        for (int[] booking : bookings) {
            int from = booking[0];
            int end = booking[1];
            int count = booking[2];

            // 在 from 上车 count 人
            gap[from] += count;
            // 在 end + 1 下车 count 人
            gap[end + 1] -= count;
        }

        for (int i = 1; i <= n; i ++) {
            gap[i] += gap[i - 1];
        }

        return Arrays.copyOfRange(gap, 1, n + 1);

    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：