差分介绍

• 对数组的某一段进行增减操作，通过差分可以在o(n)时间完成
• 每个点上记录变化数值，因为有增加有减少，通过求和判断是否有超过指定容量的情况发生，超过则代表无法满足要求。

示例

如：trips = [[2,1,5],[3,3,7]]

• 1：更新array[1] = 2, array[5] = -2;
• 2：更新array[3] = 3, array[7] = -3;
• 3：进行求和,得到结果array[] = {0,2,2,5,5,3,3,0};

典型题

leetcode 1094 拼车

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] pre = new int[1001];
        for (int[] trip : trips) {
            pre[trip[1]] += trip[0];
            pre[trip[2]] -= trip[0];
        }
        for (int i = 1; i <= 1000; i++) {
            pre[i] += pre[i - 1];
            if (pre[i] > capacity) {
                return false;
            }
        }
        return true;
    }
}

leetcode 121

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (int price : prices) {
            if (min > price) {
                min = price;
            } else {
                int temp = price - min;
                res = res > temp ? res : temp;
            }
        }
        return res;
    }
}

leetcode 122

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int res = 0;
        if (len <= 1) {
            return res;
        }
        int[] changes = new int[len - 1];
        for (int i = 1; i < len; i++) {
            changes[i - 1] = prices[i] - prices[i - 1];
            if (changes[i - 1] > 0) {
                res += changes[i - 1];
            }
        }
        return res;
    }
}

leetcode 1109

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n + 1];
        for (int[] booking : bookings) {
            res[booking[0] - 1] += booking[2];
            res[booking[1]] -= booking[2];
        }
        for (int i = 1; i < n; i++) {
            res[i] += res[i - 1];
        }
        res = Arrays.copyOfRange(res, 0, n);
        return res;
    }
}