侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【差分数组】区间加法「差分数组基础」

GabrielxD
2022-10-11 / 0 评论 / 0 点赞 / 20 阅读 / 638 字 / 正在检测是否收录...

题目

370. 区间加法


假设你有一个长度为 n 的数组,初始情况下所有的数字均为 0,你将会被给出 k​​​​​​ 个更新的操作。

其中,每个操作会被表示为一个三元组:[startIndex, endIndex, inc],你需要将子数组 A[startIndex … endIndex](包括 startIndex 和 endIndex)增加 inc

请你返回 k 次操作后的数组。

示例:

输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]

解释:

初始状态:
[0,0,0,0,0]

进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]

进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]

解题

方法一:差分数组

思路

差分数组裸题。

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

例如如果要对 ori 数组构造一个 diffs 差分数组,diffs[i] 就是 ori[i]ori[i-1] 之差,在差分数组 diffs 中我们只需关注变化的点,其他的点不用关心。

所以当我们希望对原数组的某一个区间 [l, r] 整体增加 delta 时,差分数组 diffs 对应的变化是:diffs[l] += deltadiffs[r+1] -= delta,并且这种操作是可以叠加的。

举个例子:对 nums = [1, 2, 3, 4, 5, 6] 中所有数全部加 1,再把从 nums[1]nums[3] 之间(包括)所有数加 3 ,此时的差分数组 diffs = [1, 3, 0, 0, -3, 0, -1],然后我们初始化变化量 diff = 0,开始遍历 nums

  • i = 0, diff += diffs[0] => diff = 1, nums[i] += diff => nums[i] = 2
  • i = 1, diff += diffs[1] => diff = 4, nums[i] += diff => nums[i] = 6
  • i = 2, diff += diffs[2] => diff = 4, nums[i] += diff => nums[i] = 7
  • i = 3, diff += diffs[3] => diff = 4, nums[i] += diff => nums[i] = 8
  • i = 4, diff += diffs[4] => diff = 1, nums[i] += diff => nums[i] = 6
  • i = 5, diff += diffs[5] => diff = 1, nums[i] += diff => nums[i] = 7

这样下来,无论区间是交叉还是嵌套,差分数组都可以高效处理。

参考:

代码

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diffs = new int[length + 1];
        for (int[] update : updates) {
            diffs[update[0]] += update[2];
            diffs[update[1] + 1] -= update[2];
        }
        int[] ans = new int[length];
        for (int i = 0, num = 0; i < length; ++i) ans[i] = num += diffs[i];
        return ans;
    }
}
0

评论区