【算法】差分数组

骑猪看日落 2023-10-07 22:37 5阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *  3.应用

> 本文参考：  
> [LABULADONG 的算法网站][LABULADONG]

## 1.概述 ##

（1）差分数组的思想与前缀和算法的非常近似（有关前置和算法的具体细节可以参考[前缀和算法][Link 1]这篇文章），其主要适用于**频繁地对原始数组的某个区间的元素进行加减操作**。

（2）例如，给定原始数组 nums = \{1, 3, -3, 4, 0, 2, 5\}，现在需要将区间 nums\[1…3\] 中的元素先全部加 2，然后再将区间 nums\[2…5\] 中的全部元素减 3，再将区间 nums\[3…4\] 中的元素全部减 2 等一系列操作，最后问数组 nums 中的元素是多少？

*  常规思路比较容易想到，如果将区间 nums\[1…3\] 中的元素先全部加 2，那么直接使用 for 循环对该区间中的元素进行加 2 即可，其余地操作类似，但是这样**需要进行多次时间复杂度为 O(n) 的操作**，效率比较低。
 *  而如果使用差分数组，则会较大地提高效率，话不多说，直接查看下面的实现代码。

## 2.代码实现 ##

（1）实现代码如下：

class DiffArray {
        
        //差分数组 diff
        private int[] diff;
        
        //构造差分数组 diff
        public DiffArray(int[] nums) {
        
            // diff[i] = nums[i] - nums[i - 1]
            diff = new int[nums.length];
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                diff[i] = nums[i] - nums[i - 1];
            }
        }
        
        //通过差分数组 diff 得到原数组 nums
        public int[] getNums() {
        
            int[] nums = new int[diff.length];
            nums[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
        
                nums[i] = nums[i - 1] + diff[i];
            }
            return nums;
        }
        
        //给闭区间 nums[i...j] 中的全部元素加 val (可以是负数)
        public void increase(int i, int j, int val) {
        
            diff[i] += val;
            //如果 j+1 >= diff.length，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了
            if (j + 1 < diff.length) {
        
                diff[j + 1] -= val;
            }
        }
    }

（2）下面对代码中一些细节进行说明：

*  构造差分数组 diff 时，当 i = 0 时，diff\[0\] = nums\[0\]；否则 diff\[i\] 记录 nums\[i\] 与 nums\[i - 1\] 之差，如下图所示：

![在这里插入图片描述][78ba51688de84417b609af44c6f875cc.png]

*  通过差分数组 diff 得到原数组 nums 时，当 i = 0 时，nums\[0\] = diff\[0\]；否则，由 diff\[i\] = nums\[i\] - nums\[i - 1\] 可知 nums\[i\] = diff\[i\] + nums\[i - 1\]，因此可以通过差分数组 diff 来倒推得到原数组 nums。
 *  如果想对区间 nums\[i…j\] 中的全部元素都加 3，那么只需要让 diff\[i\] += 3，然后再让 diff\[j+1\] -= 3 即可。

![在这里插入图片描述][b1445d57179b4aa9acb57c86107a6718.png]

*  原理如下：在通过差分数组 diff 倒推数组 nums 的过程中，**diff\[i\] += 3 表示给 nums\[i…\] 所有的元素都加了 3，diff\[j+1\] -= 3 又意味着对于 nums\[j+1…\] 所有元素再减 3，那么将两者结合起来，就是对 nums\[i…j\] 中的所有元素都加 3 了**。当频繁地对数组 nums 的某个区间的元素进行加减操作时，只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。多次修改 diff 后，再通过 diff 倒推，即可得到数组 nums 修改后的结果。

## 3.应用 ##

（1）有些算法题可能需要对题目进行分析，从题目中抽象出需要频繁操作的区间，从而再使用差分数组来解题，例如 LeetCode 中的[1109.航班预订统计][1109.]这题，就需要对题目进行仔细分析：

![在这里插入图片描述][6c73a919588444b0ac1b6a9284a98df8.png]

将本题翻译一下：**给定一个长度为 n 的数组 nums，初始时其中的所有元素都是 0。然后再给定一个二维数组 bookings，里面是若干三元组(i, j, k)，每个三元组的含义就是要求给 nums 数组的闭区间 \[i - 1, j - 1\] 中所有元素都加上 k，返回修改后的数组 nums**。具体的实现代码如下：

class Solution {
        
        public int[] corpFlightBookings(int[][] bookings, int n) {
        
            int[] nums = new int[n];
            DiffArray df = new DiffArray(nums);
            for (int[] booking : bookings) {
        
                int i = booking[0] - 1;
                int j = booking[1] - 1;
                int val = booking[2];
                //将区间 nums[i...j] 内的所有元素增加 val
                df.increase(i, j, val);
            }
            return df.getNums();
        }
    }
    
    class DiffArray {
        
        //差分数组 diff
        private int[] diff;
        
        //构造差分数组 diff
        public DiffArray(int[] nums) {
        
            // diff[i] = nums[i] - nums[i - 1]
            diff = new int[nums.length];
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                diff[i] = nums[i] - nums[i - 1];
            }
        }
        
        //通过差分数组 diff 得到原数组 nums
        public int[] getNums() {
        
            int[] nums = new int[diff.length];
            nums[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
        
                nums[i] = nums[i - 1] + diff[i];
            }
            return nums;
        }
        
        //给闭区间 nums[i...j] 中的全部元素加 val (可以是负数)
        public void increase(int i, int j, int val) {
        
            diff[i] += val;
            //如果 j+1 >= diff.length，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了
            if (j + 1 < diff.length) {
        
                diff[j + 1] -= val;
            }
        }
    }

（2）大家可以去 LeetCode 上找相关的差分数组题目来练习，或者也可以直接查看 [LeetCode算法刷题目录（Java）][LeetCode_Java]这篇文章中的差分数组章节。如果大家发现文章中的错误之处，可在评论区中指出。

[LABULADONG]: https://labuladong.gitee.io/algo/
[Link 1]: https://blog.csdn.net/weixin_43004044/article/details/128605676
[78ba51688de84417b609af44c6f875cc.png]: https://img-blog.csdnimg.cn/78ba51688de84417b609af44c6f875cc.png
[b1445d57179b4aa9acb57c86107a6718.png]: https://img-blog.csdnimg.cn/b1445d57179b4aa9acb57c86107a6718.png
[1109.]: https://leetcode-cn.com/problems/corporate-flight-bookings
[6c73a919588444b0ac1b6a9284a98df8.png]: https://img-blog.csdnimg.cn/6c73a919588444b0ac1b6a9284a98df8.png
[LeetCode_Java]: https://blog.csdn.net/weixin_43004044/article/details/122477673