1046. The weight of the last stone

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.

Tip:

1 <= stones.length <= 30 1 <= stones[i] <= 1000

Analysis of the

  • By analyzing problems that can be solved using maximum priority queues,
  • useleetcodSelf containedpriority-queue
  • Using theenqueueThe team,dequeueOut of the team,isEmptyTo empty the API
  • {priority: 8, element: ‘st’}

Pseudo code

  • definepqInitialization,new MaxPriorityQueue
  • traversestonesThe valueenqueueThe teampq
  • throughdequeueGet the maximum of two lines and assign values toA and bNow you can go througha["priority"]Get the value
  • Determine if thea > bA. that B. that C. that D. thatenqueueThe teama-b
  • Repeat untilpqReturns the result if there is only one value or no value in
  • whenpqReturns if there is no value in0
  • Otherwise return the value of the current element

Code implementation

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    const pq = new MaxPriorityQueue()

    for(let stone of stones){
         pq.enqueue('st',stone)
    }
    while(pq.size() > 1){
        const a = pq.dequeue()["priority"];
        const b = pq.dequeue()["priority"];
        if(a > b){
            pq.enqueue('st',a-b)
        }
    }
     return pq.isEmpty() ? 0 : pq.dequeue()["priority"]
}
Copy the code