1046. Last Stone Weight

Leetcode link

解题思路

本题一直要求我们重复取最大的两个石头，所以第一个想到的就是优先队列了。

我们只需要在石头数量大于 1 颗的时候，重复 “取两个石头，相撞，把剩下的放进优先队列” 这几个步骤就好。

最后判断一下如果还有石头就输出石头的重量，如果没有就输出 0。

C++

class Solution {
 public:
  int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> pq(stones.begin(), stones.end());
    while (pq.size() > 1) {
      int y = pq.top();
      pq.pop();
      int x = pq.top();
      pq.pop();
      if (x != y) {
        pq.push(y - x);
      }
    }
    return pq.empty() ? 0 : pq.top();
  }
};

Javascript

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
    let pq = new PriorityQueue(stones);
    while (pq.size() > 1) {
        let y = pq.top();
        pq.pop();
        let x = pq.top();
        pq.pop();
        if (x !== y) {
            pq.push(y - x);
        }
    }
    return pq.size() > 0 ? pq.top() : 0;
};

// 简单的优先队列类
class PriorityQueue {
    constructor(arr) {
        if (Array.isArray(arr) && arr.length > 0) {
            this.queue = arr.sort((a, b) => b - a);
            return;
        }
        this.queue = [];
    }

    top() {
        return this.queue[0];
    }

    pop() {
        this.queue.shift();
    }

    push(num) {
        if (this.queue.length === 0 || num > this.queue[0]) {
            this.queue.unshift(num);
            return;
        } else if (num <= this.queue[this.queue.length - 1]) {
            this.queue.push(num);
            return;
        }

        for (let i = 0; i < this.queue.length - 1; i++) {
            if (this.queue[i] >= num && this.queue[i + 1] < num) {
                this.queue.splice(i+1, 0, num);
                return;
            }
        }
    }

    empty() {
        return this.queue.length === 0;
    }

    size() {
        return this.queue.length;
    }
}