---
# System prepended metadata

title: 1046. Last Stone Weight

---


# 1046. Last Stone Weight
[1046. Last Stone Weight](https://leetcode.com/problems/last-stone-weight/) (<font color="#00AF9B"> Easy</font> 通過率: 65.7%)



## 限制條件
<ul>
<li>1 <= stones.length <= 30</li>
<li>1 <= stones[i] <= 1000</li>
</ul>




### 解法 1
這題要解的是每次找最大的兩個數去相減，然後直到整個數列不見為止，最後一個數字做為答案。
所以用 heap 做最好了，可以大大加速，所以使用 priority_queue 作為資料結構，可以大大加速

- 時間複雜度: O(nlogn)
- 空間複雜度: O(n)

```cpp!=
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> heap;
        for (auto& num : stones) {
            heap.emplace(num);
        }

        while (heap.size()) {
            int num1 = heap.top();
            heap.pop();
            if (heap.size() == 0)
                return num1;
            int num2 = heap.top();
            heap.pop();
            if (num1 - num2)
                heap.emplace(num1 - num2);
        }
        return 0;
    }
};
```
