差分?jǐn)?shù)組

有這么一類場景背率，需要頻繁對(duì)數(shù)組nums的區(qū)間[i,j]中的每個(gè)元素做加減法。比如：先對(duì)區(qū)間[a, b]的每個(gè)元素值加3嫩与，再對(duì)[a+1, b-1]的每個(gè)元素值減2寝姿。按照常規(guī)的思路，我們會(huì)想著直接上for循環(huán)一個(gè)一個(gè)進(jìn)行加減來解決蕴纳，于是寫出代碼如下：

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

上面代碼会油，如果只是增減個(gè)一兩次還好，然而當(dāng)需要頻繁增減時(shí)古毛，這樣的時(shí)間復(fù)雜度未免過高翻翩。假設(shè)需增減M次，由于每次增減操作平均時(shí)間復(fù)雜度要去到O(N)稻薇，最終就會(huì)導(dǎo)致整體時(shí)間復(fù)雜度去到O(M*N)嫂冻。

一、差分?jǐn)?shù)組

定義

差分?jǐn)?shù)組是一個(gè)與原來數(shù)組具有相等長度的數(shù)組塞椎，其第i個(gè)位置的值桨仿，表示原數(shù)組中第i個(gè)位置值減去原數(shù)組第i-1個(gè)位置的值。簡而言之案狠，緩存了原數(shù)組中相同索引元素與其上一個(gè)元素的差服傍。

如果我們定義diff為原數(shù)組nums的差分?jǐn)?shù)組，那么兩個(gè)數(shù)組的關(guān)系有：

公式1：

diff[0] = nums[0]; // 當(dāng)i=0
diff[i] = nums[i] - nums[i - 1]; // 當(dāng)i > 0

從上面公式可以看出骂铁，我們完全可以根據(jù)差分?jǐn)?shù)組反過來推算出原有數(shù)組吹零，也就可推算出 公式2：

nums[0] = diff[0]; // 當(dāng)i=0
nums[i] = diff[i] + nums[i - 1]; // 當(dāng)i > 0

根據(jù)公式，我們可以定義一個(gè)差分?jǐn)?shù)組的工具類如下：

public class Difference {

    // 差分?jǐn)?shù)組
    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];
        }
    }

    /**
     * 給區(qū)間[i,j]拉庵，增加val（可為負(fù)數(shù)）
     *
     * @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;
        }
    }

    /**
     * 構(gòu)建并返回結(jié)果數(shù)組
     *
     * @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灿椅、在工具類的構(gòu)造器中，我們通過傳入原數(shù)組nums，以及借助公式1可以構(gòu)建出差分?jǐn)?shù)組diff茫蛹。
2操刀、重點(diǎn)方法increment(int i, int j, int val)則用來處理區(qū)間元素的增減，其增減步驟為：每次往區(qū)間[i, j]增加一個(gè)數(shù)k時(shí)婴洼，則做以下操作：
diff[i] += k;
diff[j + 1] -= k;
這一步骨坑，直接將區(qū)間增減操作O(N)的時(shí)間復(fù)雜度直接降至O(1)。
3窃蹋、result()方法用于獲取增減后的結(jié)果數(shù)組卡啰，即借助于公式2，我們可以根據(jù)差分?jǐn)?shù)組倒推出原數(shù)組警没。

這樣一來匈辱，我們就不需要每次對(duì)[i, j]區(qū)間增減一個(gè)數(shù)就遍歷一次[i, j]的區(qū)間，而只需更新差分?jǐn)?shù)組diff中索引下標(biāo)為i以及j + 1的元素即可杀迹。最終通過調(diào)用result()方法亡脸，即可由差分?jǐn)?shù)組倒推出結(jié)果數(shù)組。

二树酪、通過差分?jǐn)?shù)組來解決“航班預(yù)定”問題

leetcode 1109. 航班預(yù)定統(tǒng)計(jì)

image.png

這道題完全就可以使用差分?jǐn)?shù)組的思想來解答浅碾，通過題意我們得到幾個(gè)要素：

航班數(shù)量n（數(shù)組長度）
每份預(yù)定表的座位數(shù)量 seatsi，以及起止點(diǎn)（firsti续语、lasti）

為啥說符合構(gòu)建以及使用差分?jǐn)?shù)組的思路垂谢？我們可以從中找到兩個(gè)切入點(diǎn)：

數(shù)組的長度確定了（n），那么我們就知道應(yīng)該初始化多長的數(shù)組給到差分?jǐn)?shù)組工具類的構(gòu)造器
區(qū)間的邊界i（firsti）疮茄、j（lasti）滥朱，以及增減值k（seatsi）都確定了，我們就能夠通過循環(huán)來調(diào)用increment方法來對(duì)差分?jǐn)?shù)組進(jìn)行增減力试。

最后返回結(jié)果即可徙邻。

借助于我們前面編寫出來的工具類`Difference`，實(shí)現(xiàn)代碼如下：

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才是數(shù)組中的實(shí)際索引i
            int j = booking[1] - 1;// j
            int k = booking[2];// 要增畸裳、減的值
            diff.increment(i, j, k);
        }
        return diff.result();
    }

}

三缰犁、通過差分?jǐn)?shù)組，解決“1094拼車”問題

leetcode 1094. 拼車