1046.md

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;
	}
}