[数据结构与算法]差分数组、前缀和

一、题目 —— Leetcode1109、航班预订统计

二、思路 —— 差分数组+前缀和

图解

代码

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // 计算差分数组
        int[] res = new int[n];
        for (int[] booking:bookings) {
            res[booking[0]-1] += booking[2];
            if (booking[1]<n) {
                res[booking[1]] -=booking[2];
            }
        }      
        // 计算前缀和，恢复返回的数组
        for (int i = 1;i<res.length;i++) {
            res[i]+=res[i-1];
        }
        return res;
    }
}

三、题目 —— Leetcode1094、拼车

提示：
你可以假设乘客会自觉遵守 “先下后上” 的良好素质
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

四、思路 —— 差分数组、前缀和

示例一图解

代码：

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // 计算拆分数组
        int[] res = new int[1001];
        for(int[] trip:trips) {
            res[trip[1]] += trip[0];
            res[trip[2]] -= trip[0];
        }

        // 统计每一站还剩多少人，大于capacity则返回false
        int total = 0;
        for (int person : res) {
            total += person;
            if (total > capacity) {
                return false;
            }
        }
        return true;
    }
}

总结：

对数组的某一段进行增减操作，通过差分可以在o(n)时间完成。