【算法】差分数组

差分数组

示例

originArr: [1,2,5,7,23,4,78]
differenceArr: [1,1,3,2,16,-19,74]

D[n] = O[n] - O[n-1]
eg: -19 = 4 - 231.特点1.1关系

原数组第n项 == 差分数组前n项和

\( 由D[n] = O[n] - O[n-1] , O[0] = D[0] \)
=> \( O[n] = D[n] + O[n-1] \)
=> \( O[n] = D[n] + D[n-1] + ... + O[0] \)
=> \( O[n] \) = \( \sum_{i=0}^nD[i] \)
eg: \( 7 = 1 + 1 + 3 + 2 \)1.2 前缀和 (下标从0开始计算)

原数组前n+1项和 == 差分数组第i项值*(n-i+1) 逐项累加

\( \sum_{i=0}^{n}O[i] = \sum_{i=0}^n\sum_{j=0}^iD[i] \)
=> \( \sum_{i=0}^nO[i] = D[0] + (D[0] + D[1]) + ...+ (D[0] + D[1] + ... + D[n]) \)
=> \( \sum_{i=0}^nO[i] = \sum_{i=0}^n(n-i+1)D[i] \)
eg: \( 1 + 2 + 5 + 7 = 1 × (3 - 0 +1) + 1×3 + 3×2 + 2×1 \)1.3区间操作由于原数组的值可由差分数组前缀和求得如果对一个区间同时加一个数 只需要在差分数组区间第一项加上该数为保证区间后不变 需要在区间后一项减去该数

\( O[l]+x,O[l+1]+x ... O[r]+x => D[l]+x,D[r+1]-x \)
eg: 2~5 均+10

originArr: [1,2,5,7,23,4,78]
differenceArr: [1,1,3,2,16,-19,74]
// 从 2 - 5 同时加10
originArr: [1,2,15,17,33,14,78] // 15 17 33 14
differenceArr: [1,1,13,2,16,-19,64] // 13 64
// 如果每一项都加1 那么仅需在差分数组的第一项加1 就可以维护原数组

所以针对有频繁的区间加减操作时 使用差分数组可将每次操作时间复杂度控制在\( O(1) \)
维护差分数组一般下标作为值，真实值作为计数，由于下标从0开始并且需要维护最后一位，差分数组的长度一般为最大值+22 应用

一般应用于一个状态针对某区间的统一贡献值，求最小或最大贡献值或者区间值
差分数组的值一般初始化为0，针对每个状态进行不同区间的贡献值计数，前缀和求解
关键：状态值/状态索引 与 区间贡献的对应关系

2.1 将区间分为最少组数描述
给多个闭区间，将无交集的区间划分成一组，求最小划分数

示例

[[5,10],[6,8],[1,5],[2,3],[1,10]]
//划分
[[2,3],[5,10]]
[[1,5],[6,8]]
[1,10]
// 结果为3

分析
无交集的区间划分成一组
=> 有交集的时候新加一组或者加在其他无交集的组中
=> 最小划分数 == 子区间最大重叠次数

对于示例可以进行不同的划分，但最小的划分数一定等于区间最大重叠数
有交集的区间必须在不同的组，无交集的区间在这些组内任意安排

实现
最大区间
差分区间覆盖
前缀和求最大区间覆盖数

var minGroups = function(intervals) {
  let max = 0
  let res = 0
  let cur = 0
  for(let i of intervals){
      max = Math.max(i[1],max)
  }
  // 初始化差分数组
  let area = new Array(max+2).fill(0)
  // 区间内所有元素+1 表示被覆盖的计数
  for(let i of intervals){
      area[i[0]]++
      area[i[1]+1]--
  }
  // 前缀和求元素最大覆盖数
  for(let i of area){
      cur += i
      res = Math.max(cur,res)
  }
  return res
};

2.2 使数组互补的最少操作次数描述
给定一个长度为偶数\( n \)的整数数组\( nums \)，与一个限制数\( limit \)，求令数组互补的最小变化数。
互补：所有\( nums[i] + nums[n-i-1] \)的值相等 \( eg:[1,2,2,3],sum = 1+3 = 2+2 = 4 \)
限制：\( nums[i] \) \( \in \) \( [1,limit] \)

示例

nums = [1,2,3,3] limit = 4
1
只需要将nums[2] = 2即可

分析
由 \( sum = nums[i] + nums[n-i-1] \) ; \( nums[i] \) \( \in \) \( [1,limit] \)
\( => \) \( sum \)\( \in \) \( [2,2limit] \)
设\( x \)\( \in \)\( [2,2limit] \), \( a = nums[i] \), \( b = nums[n-i-1] \)且 \( a \) \( \leq \) \( b \) ,\( times \)为满足\( a + b = x \) 的修改次数

当 \( x = a + b \) 时, \( times = 0 \)当 \( x \) \( \in \) \( [1+a,a+b) \) \( \bigcup \) \( (a+b,b+limit] \)时,\( times = 1 \)

当 \( x \) \( \in \) \( [2,2limit] \)且不在上述范围时，\( times = 2 \)

从\( a+b \)向外扩散：1、都不用修改，2、修改两个中间一个，3、两个都需要修改
\( [1+a,a+b) \) : b最小取到1 , \( (a+b,b+limit] \) : a最大取到limit;超出这个范围单独修改一个数据无法满足条件

那么，我们遍历每一对数据，针对上述3钟不同的区间进行分别计数，最终可以得到每个\( sum \)需要的修改次数，取最小值即可

每次的遍历对\( a+b \)能够出现的所有情况进行分类讨论，进行不同的加操作
由于是中心扩散，所以可以先对最大范围+2，向内逐次 -1 这样就可以利用差分进行连续的区间修改
全部遍历完成后，最终结果是数组针对每个\( sum \)为满足\( sum = nums[i]+nums[n-i-1] \)\( (i \)\( \in \)\( [0, \)\( \frac{n}{2} \)\( ]) \)成立所需要的修改次数

[1,2,3,3] 4
sum可取范围 [2,3,4,5,6,7,8] 计数 [0,0,0,0,0,0,0]
1 3 : [2,2,2,2,2,2,2] [1,1,1,1,1,1,2] [1,1,0,1,1,1,2]
2 3 : [3,3,2,3,3,3,4] [3,2,1,2,2,2,4] [3,2,1,1,2,2,4]
最终结果：[3,2,1,1,2,2,4] 可以看出当将sum = 4 或 5 时仅需要修改一次
最小修改次数为 1

这种连续的区间操作我们可是使用差分数组来优化

代码
差分数组初始化 建立长度为\( 2limit+2 \)的初始值为0数组
区间修改 每一对针对不同的区间进行修改
最小值 求前缀和的最小值

var minMoves = function(nums, limit) {
  let max = 2*limit
  // 下标最大取值2*limit 则长度为2*limit+1 由于差分维护需要后一位则长度为 2*limit + 2 
  let diff = new Array(max + 2).fill(0)

  // 区间操作
  let n = nums.length
  for(let i=0;i<n/2;i++){
      let a = Math.min(nums[i],nums[n-i-1]),b= Math.max(nums[i],nums[n-i-1])
      // [2,2*limit] + 2
      diff[2]+=2
      diff[max+1] -= 2
      
      // [1+a,limit+b] -1
      diff[1+a]--
      diff[limit+b+1]++

      // [a+b] -1
      diff[a+b]--
      diff[a+b+1]++
  }

  // 取值在[2,2*limit]的前缀和的最小值
  let res = n
  let cur = 0
  for(let i = 2;i<=max;i++){
      cur+= diff[i]
      res = Math.min(cur,res)
  }
  return res
};

其他
描述绘画结果
得分最高的最小轮调