502.IPO

链接：502.IPO
难度：Hard
标签：贪心、数组、排序、堆（优先队列）
简介：从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

题解 1 - typescript

• 编辑时间：2021-09-08
• 执行用时：336ms
• 内存消耗：66.9MB
• 编程语言：typescript
• 解法介绍：利用堆快速找出当前利润最大值。

class Heap<T = number> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
  *[Symbol.iterator](): IterableIterator<T> {
    for (const t of this.arr) {
      yield t;
    }
  }
}
type Data = {
  cost: number;
  profit: number;
};
function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number {
  const n = profits.length;
  const list: Data[] = [];
  for (let i = 0; i < n; i++)
    list.push({
      cost: capital[i],
      profit: profits[i],
    });
  list.sort((a, b) => a.cost - b.cost);
  const heap = new Heap<Data>((t1, t2) => t1.profit - t2.profit);
  if (w >= list[list.length - 1].cost) {
    return list
      .sort((a, b) => b.profit - a.profit)
      .slice(0, k)
      .reduce((total, cur) => (total += cur.profit), w);
  }
  let idx = 0;
  while (k > 0) {
    while (idx < n && list[idx].cost <= w) {
      heap.add(list[idx++]);
    }
    if (heap.size === 0) break;
    const data = heap.remove();
    w += data.profit;
    k--;
  }
  return w;
}