857.雇佣-k-名工人的最低成本.md

857.雇佣-k-名工人的最低成本

/*
 * @lc app=leetcode.cn id=857 lang=typescript
 *
 * [857] 雇佣 K 名工人的最低成本
 */

// @lc code=start
function mincostToHireWorkers(quality: number[], wage: number[], k: number): number {}
// @lc code=end

解法 1: 自定义排序 + 枚举

function mincostToHireWorkers(quality: number[], wage: number[], k: number): number {
  const n = quality.length
  const a = quality
    .map((a, i) => [wage[i] / a, a])
    .sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : quality[b[1]] - quality[a[1]]))

  const cur = new BinarySearchTree()

  let res = Infinity,
    sum = 0
  for (let i = 0; i < k - 1; i++) {
    cur.insert(a[i][1])
    sum += a[i][1]
  }

  for (let i = k - 1; i < n; i++) {
    sum += a[i][1]
    res = Math.min(res, a[i][0] * sum)
    cur.insert(a[i][1])
    sum -= cur.getMax()!
    cur.delete(cur.getMax()!)
  }
  return res
}

interface BSTNode<T = number> {
  id: number
  val: T
  size: number
  height: number
  count: number
  left: BSTNode<T> | null
  right: BSTNode<T> | null
}
/**
 * @see https://github.com/XYShaoKang/sk-js-algorithm
 */
class BinarySearchTree<T = number> {
  private root: BSTNode<T> | null = null
  /**
   * 不重复数字的个数
   */
  private length = 0
  private min: T | null = null
  private max: T | null = null
  private minCache = true
  private maxCache = true
  constructor(...args: T extends number ? [((a: number, b: number) => number)?] : [(a: T, b: T) => number])
  constructor(private _compare: (a: T, b: T) => number = ((a: number, b: number) => a - b) as any) {
    this.compare = this.compare.bind(this)
  }
  private isT(t: T | undefined | null): t is T {
    return t !== undefined && t !== null
  }
  private compare(a: T | null | undefined, b: T | null | undefined) {
    const { isT } = this
    if (isT(a) && isT(b)) return this._compare(a, b)

    if (isT(a)) return 1
    if (isT(b)) return -1
    return 0
  }
  /** 判断是否为空
   */
  isEmpty() {
    return !this.root
  }
  /** 获取所有元素个数,统计的是包含所有重复数字的数量
   */
  size() {
    return this.root ? this.root.size : 0
  }
  /** 返回树的 root 元素
   */
  getRoot() {
    return this.root
  }
  /** # 返回最小值
   *  如果之前发生删除,并且删除的数等于最小值,则会在下次获取最小值时,重新查找最小值,并缓存最小值
   *  否则直接返回缓存中的最小值
   */
  getMin(): T | null {
    if (this.minCache) {
      return this.min
    }
    const min = this.searchKth(this.size())
    this.min = min
    this.minCache = true
    return min
  }
  /** # 返回最大值
   *  如果之前发生删除,并且删除的数等于最大值,则会在下次获取最大值时,重新查找最大值,并缓存最大值
   *  否则直接返回缓存中的最大值
   */
  getMax(): T | null {
    if (this.maxCache) {
      return this.max
    }
    const max = this.searchKth(1)
    this.max = max
    this.maxCache = true
    return max
  }

  //#region balance
  /**
   * 平衡操作
   * @param node 失衡的根结点
   * @returns 返回平衡之后的根结点
   */
  private balance(node: BSTNode<T>): BSTNode<T> {
    node.height = this.getHeight(node)
    const blance = this.getBalance(node)
    // node.height = Math.max(leftH, rightH) + 1
    let res
    // 平衡
    if (Math.abs(blance) === 2) {
      if (blance > 0) {
        const heightDif = (node.left?.left?.height ?? 0) - (node.left?.right?.height ?? 0)
        if (heightDif > 0) {
          // 左左
          res = this.rotateRight(node)
        } else if (heightDif < 0) {
          // 左右
          res = this.rotateLeftRight(node)
        }
      } else {
        const heightDif = (node.right?.left?.height ?? 0) - (node.right?.right?.height ?? 0)
        if (heightDif > 0) {
          // 右左
          res = this.rotateRightLeft(node)
        } else if (heightDif < 0) {
          // 右右
          res = this.rotateLeft(node)
        }
      }
    }
    return res ? res : node
  }
  private rotateRight(node: BSTNode<T>) {
    const left = node.left!
    const leftRight = left.right

    left.right = node
    node.left = leftRight

    node.height = this.getHeight(node)
    left.height = this.getHeight(left)
    node.size = this.getSize(node)
    left.size = this.getSize(left)

    return left
  }
  private rotateLeft(node: BSTNode<T>) {
    const right = node.right!
    const rightLeft = right.left

    right.left = node
    node.right = rightLeft

    node.height = this.getHeight(node)
    right.height = this.getHeight(right)
    node.size = this.getSize(node)
    right.size = this.getSize(right)

    return right
  }
  private rotateLeftRight(node: BSTNode<T>) {
    node.left = this.rotateLeft(node.left!)
    return this.rotateRight(node)
  }
  private rotateRightLeft(node: BSTNode<T>) {
    node.right = this.rotateRight(node.right!)
    return this.rotateLeft(node)
  }

  //#endregion

  private getBalance(node: BSTNode<T>) {
    return this.getHeight(node.left) - this.getHeight(node.right)
  }
  private getHeight(node: BSTNode<T> | null) {
    if (!node) return 0
    return Math.max(node.left?.height ?? 0, node.right?.height ?? 0) + 1
  }
  private getSize(node: BSTNode<T> | null) {
    if (!node) return 0
    return (node.left?.size ?? 0) + (node.right?.size ?? 0) + node.count
  }

  private createNode(val: T): BSTNode<T> {
    return { id: Math.random() * new Date().valueOf(), val, left: null, right: null, size: 1, height: 1, count: 1 }
  }
  /** 插入元素
   */
  insert(val: T) {
    let cur = this.createNode(val)
    if (this.isEmpty()) {
      this.root = cur
      this.length++
    } else {
      ;[, cur] = this.insertNode(this.root!, cur)
    }

    if (this.min === null || this.compare(this.min, val) > 0) {
      this.min = val
    }
    if (this.max === null || this.compare(this.max, val) < 0) {
      this.max = val
    }
  }
  /**
   *
   * @param node 当前遍历的结点
   * @param cur 需要插入的结点
   * @param parent 当前结点的父节点
   * @returns 返回包含一个 boolean 值,用来标记是否需要重平衡,以及插入的 Node,如果是重复值,则返回已经存在的那个 Node
   */
  private insertNode(node: BSTNode<T>, cur: BSTNode<T>, parent: BSTNode<T> | null = null): [boolean, BSTNode<T>] {
    node.size++
    const compareResult = this.compare(cur.val, node.val)
    let res: [boolean, BSTNode<T>] | undefined
    if (compareResult === 0) {
      // 要插入的结点比当前结点相等,既元素已存在,只需更新 count
      node.count++
      // 只是增加计数,不会对平衡性造成影响,所以不需要重新平衡
      return [false, node]
    } else if (compareResult > 0) {
      // 要插入的结点比当前结点大,则需要插入到右子树中
      if (node.right) {
        res = this.insertNode(node.right, cur, node)
        if (!res[0]) return res
      } else {
        node.right = cur
        this.length++
        res = [true, cur]
      }
    } else {
      // 要插入的结点比当前结点小,则需要插入到左子树中
      if (node.left) {
        res = this.insertNode(node.left, cur, node)
        if (!res[0]) return res
      } else {
        node.left = cur
        this.length++
        res = [true, cur]
      }
    }

    // 平衡操作
    // 优化: 使用 res[0] 标志判断是否需要进行平衡
    // 对于新添加的结点,总是需要进行平衡
    // 如果发现某个子树平衡前后的没有变化,树的高度也没有变化,则后续祖先结点不需要进行平衡操作
    let preHeight = node.height
    const newNode = this.balance(node)
    if (newNode === node && node.height === preHeight) {
      // 当前根结点以及树高度没有发生变化,则后续不需要进行平衡
      res = [false, res[1]]
    } else if (newNode !== node) {
      // 当前元素发生变化,对于插入来说,只会调整一次,后续不需要变化
      if (parent) {
        parent.left === node ? (parent.left = newNode) : (parent.right = newNode)
      } else {
        this.root = newNode
      }
      res = [false, res[1]]
    }
    return res
  }

  /** 删除元素
   */
  delete(val: T) {
    this.deleteResult = false
    if (!this.root) return this.deleteResult
    this.deleteNode(val, this.root, null)
    return this.deleteResult
  }
  private deleteResult: boolean = false
  private deleteNode(val: T, node: BSTNode<T> | null, parent: BSTNode<T> | null): BSTNode<T> | null {
    if (!node) return null

    let res = this.compare(val, node.val)
    if (res === 0) {
      this.deleteResult = true
      // 找到要删除的元素
      node.count--
      node.size--
      // 存在多个当前元素,所以只是减去计数,并不需要改变结构
      if (node.count > 0) return node

      if (!node.left || !node.right) {
        if (this.min === val) {
          this.minCache = false
        }
        if (this.max === val) {
          this.maxCache = false
        }
        this.length--
        // 只有一个子结点或者没有子结点,则直接返回子结点即可
        if (!parent) {
          this.root = node.left ?? node.right!
          return this.root
        } else {
          return node.left ?? node.right!
        }
      } else {
        // 同时存在左右结点,则需要找到一个值放到当前位置,然后删除那个值
        // 这个值可以是比当前值大的最小值,也可以是比当前值小的最大值
        // 这里根据左右子树的高度进行选择
        const selectLeft = node.left.height > node.right.height
        let replaceNode = selectLeft ? this.pre(node)! : this.next(node)!,
          name: 'left' | 'right' = selectLeft ? 'left' : 'right'

        node.val = replaceNode.val
        node.count = replaceNode.count
        replaceNode.count = 0
        node[name] = this.deleteNode(replaceNode.val, node[name], node)
      }
    } else if (res > 0) {
      node.right = this.deleteNode(val, node.right, node)
    } else {
      node.left = this.deleteNode(val, node.left, node)
    }

    // 重新计算 size
    node.size = this.getSize(node)

    let preHeight = node.height
    const newNode = this.balance(node)
    if (parent) {
      parent.left === node ? (parent.left = newNode) : (parent.right = newNode)
    } else {
      this.root = newNode
    }

    return newNode
  }
  // 删除操作时,获取替代当前结点的结点
  private next(node: BSTNode<T>) {
    let next = node.right
    while (next?.left) {
      next = next.left
    }
    return next
  }
  private pre(node: BSTNode<T>) {
    let pre = node.left
    while (pre?.right) {
      pre = pre.right
    }
    return pre
  }

  search(val: T, compare?: (a: T, b: T) => number) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchCeilingNode(this.root!, val, compare ?? this.compare)
    return node.val
  }

  private searchCeilingNode(
    node: BSTNode<T>,
    val: T,
    compare: (a: T, b: T) => number,
    parent: BSTNode<T> | null = null,
  ): [BSTNode<T> | null, BSTNode<T>] {
    const res = compare(val, node.val)
    if (res === 0) {
      return [parent, node]
    } else if (res > 0) {
      if (node.right) {
        return this.searchCeilingNode(node.right, val, compare, node)
      } else {
        return [parent, node]
      }
    } else {
      if (node.left) {
        const [p, value] = this.searchCeilingNode(node.left, val, compare, node)
        if (compare(value.val, val) < 0) {
          return [parent, node]
        } else {
          return [p, value]
        }
      } else {
        return [parent, node]
      }
    }
  }
  /** 获取大于等于 val 的最小值
   */
  ceiling(val: T) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchCeilingNode(this.root!, val, this.compare)
    return this.compare(node.val, val) >= 0 ? node.val : null
  }

  private searchFloorNode(
    node: BSTNode<T>,
    val: T,
    compare: (a: T, b: T) => number,
    parent: BSTNode<T> | null = null,
  ): [BSTNode<T> | null, BSTNode<T>] {
    const res = compare(val, node.val)
    if (res === 0) {
      return [parent, node]
    } else if (res > 0) {
      if (node.right) {
        const [p, value] = this.searchFloorNode(node.right, val, compare, node)
        if (compare(value.val, val) > 0) {
          return [parent, node]
        } else {
          return [p, value]
        }
      } else {
        return [parent, node]
      }
    } else {
      if (node.left) {
        return this.searchFloorNode(node.left, val, compare, node)
      } else {
        return [parent, node]
      }
    }
  }
  /** 获取小于等于 val 的最大值
   */
  floor(val: T) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchFloorNode(this.root!, val, this.compare)
    return this.compare(node.val, val) <= 0 ? node.val : null
  }

  /** 获取第 k 个元素的值,k 从 1 开始,如果 k 超出边界,返回 null
   */
  searchKth(k: number) {
    if (this.isEmpty()) {
      return null
    }
    if (k <= 0 || k > this.size()) {
      return null
    }
    const node = this.searchNodeKth(this.root!, k)
    return node.val
  }
  private searchNodeKth(node: BSTNode<T>, k: number): BSTNode<T> {
    const rSize = node.right?.size ?? 0
    if (rSize === k - 1 || (rSize < k && rSize + node.count >= k)) return node
    if (node.right && rSize > k - 1) return this.searchNodeKth(node.right, k)
    else return this.searchNodeKth(node.left!, k - (node.right?.size ?? 0) - node.count)
  }

  /** 统计大于等于 val 的个数
   * @param val 需要统计的值
   */
  countGreaterThanEq(val: T) {
    if (!this.root) return 0
    return this.countCompare(val, (a, b) => this._compare(a, b), this.root)
  }
  private countCompare(val: T, compare: (a: T, b: T) => number, node: BSTNode<T>, pre = 0): number {
    const res = compare(val, node.val)
    if (res === 0) {
      return pre + (node.right?.size ?? 0) + node.count
    } else if (res > 0) {
      if (node.right) {
        return this.countCompare(val, compare, node.right, pre)
      } else {
        return pre
      }
    } else {
      let count = pre + (node.right?.size ?? 0) + node.count
      if (node.left) {
        return this.countCompare(val, compare, node.left, count)
      } else {
        return count
      }
    }
  }

  /** 将 BST 转成数组,按升序排列返回
   */
  toArray(): T[] {
    if (!this.root) return []
    const res: T[] = []
    const dfs = (node: BSTNode<T>) => {
      if (node.left) dfs(node.left)
      res.push(node.val)
      if (node.right) dfs(node.right)
    }
    dfs(this.root)
    return res
  }
}

Case

test.each([
  {
    input: {
      quality: [25, 68, 35, 62, 52, 57, 35, 83, 40, 51],
      wage: [147, 97, 251, 129, 438, 443, 120, 366, 362, 343],
      k: 6,
    },
    output: 1979.31429,
  },
  { input: { quality: [3, 1, 10, 10, 1], wage: [4, 8, 2, 2, 7], k: 3 }, output: 30.66667 },
  { input: { quality: [10, 20, 5], wage: [70, 50, 30], k: 2 }, output: 105.0 },
])('input: quality = $input.quality, wage = $input.wage, k = $input.k', ({ input: { quality, wage, k }, output }) => {
  expect(Math.abs(mincostToHireWorkers(quality, wage, k) - output) <= 10 ** -5).toEqual(true)
})