java学习——差分法求解问题

基本思想：
差分法的主要是用于处理区间问题。当要对不同区间的元素进行统一操作时，为了避免多重循环引起的高复杂度，使用差分法，通过首先对区间端点元素进行操作，再通过前缀求和（当前位置元素=上一个位置元素+当前位置变化）的方式来得到一个新的数组，完成操作。

1109.航班预定统计

public int[] corpFlightBookings(int[][] bookings, int n) {

        // -------差分法求解------
        // 可以将问题转换为：求解公交车上每一站的人数
        // int[] res = new int[n];
        // count记录每一站的人数变化情况
        int[] count = new int[n];
        for (int[] booking : bookings) {
            // 乘客上车，代表在初始站预定车票
            count[booking[0] - 1] += booking[2];
            // 乘客下车, 代表在第last+1站不再预定
            if (booking[1] < n) {
                count[booking[1]] -= booking[2];
            }
        }
        // count开始只记录了乘客上下车的站点情况，
        // 那么每一站公交车上人数等于上一站的人数加上本站人数变化情况
        for (int i = 1; i < n; i++) {
            count[i] += count[i - 1];
        }
        return count;
    }