区间强度算法IntensitySegments

/**
 * 考虑到题目要求时间复杂度为O(n)，如果直接使用Map的话，排序的时间复杂度就会增加到O(nlogn)，所以自定义一个数据结构
 * orderedMap.orderedEntries 的返回值，按照key（number类型）进行排序，从小到大
 */
class OrderedMap {
  constructor() {
    /** 使用map数据结构，查找的时间复杂度为O(1) */
    this.map = new Map()
    /**
     * 额外维护一份数组的数据结构，按照key的顺序进行插入
     * 就不采用map.entries().sort()方式来获取了
     */
    this.orderedEntries = []
  }
 
  has(key) {
    return this.map.has(key)
  }
 
  get(key) {
    return this.map.get(key)
  }
 
  /** 时间复杂度O(n)，这个是为了维护一个有序的数组 */
  set(key, value) {
    /** 已经存在的情况 */
    if (this.map.has(key)) {
      const idx = this.orderedEntries.findIndex(([_key, _value]) => _key === key)
      this.orderedEntries[idx] = [key, value]
      this.map.set(key, value)
      return
    }
 
    /** 没有存在的情况，就简单的采用迭代遍历了，可以考虑使用二分进行优化 */
    let idx = -1 // 最后一个小于“权重”的下标
    for (let _index in this.orderedEntries) {
      const [_key, _value] = this.orderedEntries[_index]
      if (_key >= key) break
      idx++
    }
    this.orderedEntries.splice(idx + 1, 0, [key, value])
 
    this.map.set(key, value)
  }
 
  delete(key) {
    this.map.delete(key)
 
    const idx = this.orderedEntries.findIndex(([_key]) => _key === key)
    if (idx > -1) this.orderedEntries.splice(idx, 1)
  }
 
  entries() {
    return this.orderedEntries
  }
}
 
class IntensitySegments {
  constructor() {
    /**
     * 维护每个点的高度的相对增量的map
     * key为位置信息，pos
     * value为高度的相对增量
     */
    this.heightDiffMap = new OrderedMap()
  }
 
  /** 封装下set方法，当key对应的高度增量为0的时候，，就需要干掉key（表示该位置是冗余信息） */
  #setHeightDiffMap(key, value) {
    this.heightDiffMap.set(key, value)
    if (value === 0) this.heightDiffMap.delete(key)
  }
 
  add(from, to, amount) {
    this.#check(from, to)
    this.#setHeightDiffMap(from, (this.heightDiffMap.get(from) || 0) + amount)
    this.#setHeightDiffMap(to, (this.heightDiffMap.get(to) || 0) - amount)
  }
 
  set(from, to, amount) {
    this.#check(from, to)
    const leftHeight = this.#getLeftHeightOfPos(from)
    const rightHeight = this.#getRightHeightOfPos(to)
 
    // 删除老的高度增量，在[from, to]区间内
    this.heightDiffs.forEach(([pos]) => {
      if (from <= pos && pos <= to) {
        this.heightDiffMap.delete(pos)
      }
    })
 
    // 添加新的高度增量
    this.#setHeightDiffMap(from, amount - leftHeight)
    this.#setHeightDiffMap(to, rightHeight - amount)
  }
 
  toString() {
    return JSON.stringify(this.heights)
  }
 
  #check(from, to) {
    if (from >= to) throw new Error(`from的值必须要小于to的值, 当前from为${from}, to为${to}`)
  }
 
  /**
   * 返回的是一个有序的数组，时间复杂度为O(n)
   * @return Array<[number(位置信息), number(高度的相对增量)]>
   */
  get heightDiffs() {
    return [...this.heightDiffMap.entries()]
  }
 
  /**
   * @return Array<[number(位置信息), number(高度信息)]>
   */
  get heights() {
    const heights = []
 
    // 从0开始，根据高度的增量信息不断累加
    let current = 0
    this.heightDiffs.forEach(([pos, amount]) => {
      current += amount
      heights.push([pos, current])
    })
 
    return heights
  }
 
  /** 获取某个位置左边（线段）的高度 */
  #getLeftHeightOfPos(targetPos) {
    // 从无穷小的0开始迭代
    let prevPos = -Infinity
    let prevHeight = 0
 
    for (let [currPos, height] of this.heights) {
      // （注意左开右闭）如果目标位置在“上一个位置”和“当前位置”之间，那么目标左侧的高度就是上一个高度
      if (prevPos < targetPos && targetPos <= currPos) {
        return prevHeight
      }
 
      prevPos = currPos
      prevHeight = height
    }
 
    return prevHeight // 如果匹配到最后也没找到，就返回最后的高度
  }
 
  /** 获取某个位置右边（线段）的高度 */
  #getRightHeightOfPos(targetPos) {
    // 从无穷小的0开始迭代
    let prevPos = -Infinity
    let prevHeight = 0
 
    for (let [currPos, height] of this.heights) {
      // （注意左闭右开）如果目标位置在“上一个位置”和“当前位置”之间，那么目标右侧的高度就是上一个高度
      if (prevPos <= targetPos && targetPos < currPos) {
        return prevHeight
      }
 
      prevPos = currPos
      prevHeight = height
    }
 
    return prevHeight // 如果匹配到最后也没找到，就返回最后的高度
  }
}