差分数组

有这么一类场景，需要频繁对数组nums的区间[i,j]中的每个元素做加减法。比如：先对区间[a, b]的每个元素值加3，再对[a+1, b-1]的每个元素值减2。按照常规的思路，我们会想着直接上for循环一个一个进行加减来解决，于是写出代码如下：

public void increment(int[] nums, int i, int j, int k) {
    for(int idx = i; i <= j; i++) {
        nums[idx] += k;
    }
}

上面代码，如果只是增减个一两次还好，然而当需要频繁增减时，这样的时间复杂度未免过高。假设需增减M次，由于每次增减操作平均时间复杂度要去到O(N)，最终就会导致整体时间复杂度去到O(M*N)。

一、差分数组

定义

差分数组是一个与原来数组具有相等长度的数组，其第i个位置的值，表示原数组中第i个位置值减去原数组第i-1个位置的值。简而言之，缓存了原数组中相同索引元素与其上一个元素的差。

如果我们定义diff为原数组nums的差分数组，那么两个数组的关系有：

公式1：

diff[0] = nums[0]; // 当i=0
diff[i] = nums[i] - nums[i - 1]; // 当i > 0

从上面公式可以看出，我们完全可以根据差分数组反过来推算出原有数组，也就可推算出 公式2：

nums[0] = diff[0]; // 当i=0
nums[i] = diff[i] + nums[i - 1]; // 当i > 0

根据公式，我们可以定义一个差分数组的工具类如下：

public class Difference {

    // 差分数组
    private int[] diff;

    public Difference(int[] nums) {
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < diff.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /**
     * 给区间[i,j]，增加val（可为负数）
     *
     * @param i
     * @param j
     * @param val
     */
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /**
     * 构建并返回结果数组
     *
     * @return
     */
    public int[] result() {
        int[] nums = new int[diff.length];
        nums[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            nums[i] = diff[i] + nums[i - 1];
        }
        return nums;
    }

}

工具类中主要分3块逻辑：

1、在工具类的构造器中，我们通过传入原数组nums，以及借助公式1可以构建出差分数组diff。
2、重点方法increment(int i, int j, int val)则用来处理区间元素的增减，其增减步骤为：每次往区间[i, j]增加一个数k时，则做以下操作：
diff[i] += k;
diff[j + 1] -= k;
这一步，直接将区间增减操作O(N)的时间复杂度直接降至O(1)。
3、result()方法用于获取增减后的结果数组，即借助于公式2，我们可以根据差分数组倒推出原数组。

这样一来，我们就不需要每次对[i, j]区间增减一个数就遍历一次[i, j]的区间，而只需更新差分数组diff中索引下标为i以及j + 1的元素即可。最终通过调用result()方法，即可由差分数组倒推出结果数组。

二、通过差分数组来解决“航班预定”问题

leetcode 1109. 航班预定统计

image.png

这道题完全就可以使用差分数组的思想来解答，通过题意我们得到几个要素：

航班数量n（数组长度）
每份预定表的座位数量 seatsi，以及起止点（firsti、lasti）

为啥说符合构建以及使用差分数组的思路？我们可以从中找到两个切入点：

数组的长度确定了（n），那么我们就知道应该初始化多长的数组给到差分数组工具类的构造器
区间的边界i（firsti）、j（lasti），以及增减值k（seatsi）都确定了，我们就能够通过循环来调用increment方法来对差分数组进行增减。

最后返回结果即可。

借助于我们前面编写出来的工具类`Difference`，实现代码如下：

class Solution {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        Difference diff = new Difference(nums);
        for (int[] booking : bookings) {
            int i = booking[0] - 1;// 要减去1才是数组中的实际索引i
            int j = booking[1] - 1;// j
            int k = booking[2];// 要增、减的值
            diff.increment(i, j, k);
        }
        return diff.result();
    }

}

三、通过差分数组，解决“1094拼车”问题

leetcode 1094. 拼车