1046.最后一块石头的重量

链接：1046.最后一块石头的重量
难度：Easy
标签：数组、堆（优先队列）
简介：有一堆石头，每块石头的重量都是正整数。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

题解 1 - typescript

• 编辑时间：2020-12-30
• 执行用时：104ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：构建堆。

var lastStoneWeight = function (stones) {
  const pq = new MaxPriorityQueue();
  for (const stone of stones) {
    pq.enqueue('x', stone);
  }
  while (pq.size() > 1) {
    const a = pq.dequeue()['priority'];
    const b = pq.dequeue()['priority'];
    if (a > b) {
      pq.enqueue('x', a - b);
    }
  }
  return pq.isEmpty() ? 0 : pq.dequeue()['priority'];
};

题解 2 - typescript

• 编辑时间：2021-04-11
• 执行用时：92ms
• 内存消耗：39.1MB
• 编程语言：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;
    }
  }
}
function lastStoneWeight(stones: number[]): number {
  const heap = new Heap((t1, t2) => t1 - t2);
  stones.forEach(v => heap.add(v));
  while (heap.size > 1) {
    const s1 = heap.remove();
    const s2 = heap.remove();
    if (s1 === s2) continue;
    heap.add(Math.abs(s1 - s2));
  }
  return heap.size === 0 ? 0 : heap.top;
}