【数组】差分数组

[miracles1919]

差分数组适合频繁对原始数组的某个区间进行增减

• 假设 diff[i] 表示 nums[i] - nums[i-1]
• 根据 diff 可以反推出原始数组

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

• 如果想对 nums[i...j] 内的元素全部 + 3，只需要 nums[i] += 3, nums[j + 1] -= 3

参考：小而美的算法技巧：差分数组

[miracles1919]

1109. 航班预订统计

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function (bookings, n) {
    const diff = new Array(n).fill(0)

    bookings.forEach((item) => {
        const [left, right, num] = item
        diff[left - 1] += num
        if (right < n) {
            diff[right] -= num
        }
    })

    const res = new Array(n).fill(0)
    res[0] = diff[0]
    for (let i = 1; i < n; i++) {
        res[i] = res[i - 1] + diff[i]
    }

    return res
};

[miracles1919]

1094. 拼车

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function (trips, capacity) {
    const maxLen = 1001
    const diff = new Array(maxLen).fill(0)
    trips.forEach(item => {
        const [num, form, to] = item
       // 乘客在车上的区间为 [form, to - 1]
        diff[form] += num
        if (to < maxLen) {
            diff[to - 1 + 1] -= num
        }
    })

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

    for (let i = 0; i < res.length; i++) {
        if (res[i] > capacity) {
            return false
        }
    }

    return res.filter(num => num > capacity).length <= 0
};