---
# System prepended metadata

title: 1046. Last Stone Weight
tags: [Leetcode, Easy, Priority Queue]

---

# 1046. Last Stone Weight
###### tags: `Leetcode` `Easy` `Priority Queue`
Link: https://leetcode.com/problems/last-stone-weight/
## 思路 $O(NlogN)$ $O(N)$
Put all elements into a priority queue.
Pop out the two biggest, push back the difference,
until there are no more two elements left.
## Code
```java=
class Solution {
    public int lastStoneWeight(int[] stones) {
        if(stones.length==1) return stones[0];
        if(stones.length==0) return 0;
        Queue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        for(int stone:stones){
            q.add(stone);
        }
        while(q.size()>1){
            int y = q.poll();
            int x = q.poll();
            if(x<y) q.add(y-x);
        }
        return q.size()==0?0:q.peek();
    }
}
```
