The title

There is a pile of stones, and each stone has a positive integer weight.

In each round, pick two of the heaviest stones and smash them together. Suppose the stones weigh x and y, and x <= y. Then the possible results of shredding are as follows:

If x == y, then both stones will be completely shattered; If x! = y, then the stone weighing x will be completely crushed, and the stone weighing Y will have a new weight of Y-x. In the end, there will be no more than one stone left. Returns the weight of this stone. If there are no stones left, 0 is returned.

Example:

Input: [2,7,4,1,8,1] First 7 and 8 get 1, so the array is converted to [2,4,1,1,1], then 2 and 4 get 2, so the array is converted to [2,1,1,1], then 2 and 1 get 1, so the array is converted to [1,1,1], then 1 and 1 get 0, The final array is converted to [1], which is the weight of the remaining rock.Copy the code

Source: LeetCode leetcode-cn.com/problems/la…

Their thinking

  1. It’s a little tricky to implement when you don’t know LeetCode has MaxPriorityQueue
  2. When you know that MaxPriorityQueue is available, it’s easy

Code implementation

var lastStoneWeight = function(stones) {
    const pq = new MaxPriorityQueue()
    stones.forEach(stone => {
        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']
};
Copy the code

If there are mistakes welcome to point out, welcome to discuss together!