差分数组

关键

写出差分数组类

模板

const diff = new Array(nums.length)

diff[0] = num[0]
// 构建差值数组后一个减去前一个值的差值
for (let i = 1; i < num.length; i++) {
  diff[i] = num[i] - nums[i - 1]
}

// 还原数组
const res = new Array(nums.length)

res[0] = diff[0]

for (let i = 1; i < nums.length; i++) {
  res[i] = res[i - 1] + diff[i]
}

手写 js 差分数组处理类

class Diff {
  // 保存原始组数
  constructor(nums) {
    this.nums = nums
    // 构建差分数组
    this.initDiff()
  }

  initDiff() {
    const diff = new Array(this.nums.length)
    diff[0] = this.nums[0]
    for (let i = 1; i < this.nums.length; i++) {
      diff[i] = this.nums[i] - this.nums[i - 1]
    }
    this.diff = diff
  }

  add(left, right, val) {
    // [left,end] +val [right+1,end] -val 就是 [left,right] + val
    this.diff[left] += val
    if (right <= this.nums.length) {
      this.diff[right + 1] -= val
    }
  }
  result() {
    const result = new Array(this.nums.length)
    result[0] = this.diff[0]
    for (let i = 1; i < this.nums.length; i++) {
      result[i] = this.diff[i] + result[i - 1]
    }
    return result
  }
}

https://leetcode.cn/problems/corporate-flight-bookings/solution/1109-hang-ban-yu-ding-tong-ji-by-yill625-5zpn/

1094. 拼车 (opens new window)

// @lc code=start
/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function (trips, capacity) {
  // 假设车能无限上人 所以就是在上车点家人 下车点减人 区间内加减 使用差分数组 只要任意一个区间大于车载数就是不能成功
  const nums = new Array(1001).fill(0)
  const diff = new Diff(nums)
  for (let i = 0; i < trips.length; i++) {
    const val = trips[i][0]
    const l = trips[i][1]
    const r = trips[i][2] - 1 //  在车上的区间

    diff.add(l, r, val)
  }
  const res = diff.result()

  return res.every((item) => item <= capacity)
}

1109. 航班预订统计 (opens new window)

// @lc code=start
/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function (bookings, n) {
  const nums = new Array(n).fill(0)
  const diff = new Diff(nums)
  for (let i = 0; i < bookings.length; i++) {
    diff.add(bookings[i][0] - 1, bookings[i][1] - 1, bookings[i][2])
  }
  return diff.result()
}