4、区间加法

INFO

区间加法 | 力扣 | LeetCode |

假设你有一个长度为 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]

// 实现一个差分数组
class Difference {
  constructor(nums) {
    // 原始数组
    this.nums = nums
    this.initDef()
  }
  initDef() {
    // 差分数组初始化
    this.diffs = [this.nums[0]]
    // 完整获取差分数组
    for(let i = 1;i<this.nums.length;i++) {
      this.diffs[i] = this.nums[i] - this.nums[i-1]
    }
  }
  /** 区间增加 */
  increment(s,e,val) {
    // 头部 +1
    this.diffs[s]+=val
    // 如果不是最后一个，则设置差分的结束地址
    if (e<this.nums.length) {
      this.diffs[e+1] -=val
    }
  }
  result() {
    const list = [this.diffs[0]]
    for(let i = 1;i<this.diffs.length;i++) {
      list[i] = this.diffs[i]  + list[i-1]
    }
   return list
  }
}

var getModifiedArray = function(length, updates) {
    // nums 初始化为全 0
    var nums = new Array(length).fill(0);
    // 构造差分解法
    var df = new Difference(nums);

    for (var i = 0; i < updates.length; i++) {
        var update = updates[i];
        df.increment(...update);
    }

    return df.result();
};

差分原理解释

有另外的数组保存原数组后面一个元素和前端元素的关系，只要知道第一个原始值，就能推出后面的所有值。