1046. Weight of the last stone

1、 Title Description

2、 title

Because you have to choose in every round 【 The two heaviest stones 】, So you need to sort every time , You can think of using ready-made data structures that can automatically sort , therefore   The thought of 【 Pile up 】 This data structure that can automatically sort .

Put all the stones into the big top pile , Then take out the two heaviest stones in turn x and y, There must be x ≥ y. If x > y, Then the new stone x - y Put it back in the largest heap ; If x = y, The two stones were completely crushed , Therefore, no new stones will be produced .

• use 【JAVA】 Realization , Statement 【 Descending 】  The big root pile is the difficulty ：
• PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);

The implementation code is as follows ：

class Solution {
    public int lastStoneWeight(int[] stones) {
        // Declare big root heap , Avoid sorting every time 
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b)->b-a);
        for(int stone : stones){
            pq.offer(stone);
        }

        while(pq.size() > 1){
            // because pq The array has been sorted before , Take the maximum two numbers each time , There is only  b<=a The possibility of 
            int a = pq.poll();
            int b = pq.poll();
            //b=a when , Two direct poll that will do , When b<a when , You need to write to the heap again （b-a） This number 
            if(b < a){
                pq.offer(a-b);
            }
        }
        return pq.isEmpty() ? 0:pq.poll();
    }
}

Complexity analysis

Time complexity ：O(nlogn), among n  Is the number of stones . Each time an element is taken out of the queue, it takes O(logn) Time for , At most, it needs to be crushed n−1 Secondary stone .

Spatial complexity ：O(n).