###### tags: `Leetcode` `easy` `heap` `python` `c++`

# 1046. Last Stone Weight

## [題目連結:] https://leetcode.com/problems/last-stone-weight/description/

## 題目:
You are given an array of integers ```stones``` where ```stones[i]``` is the weight of the ```ith``` stone.

We are playing a game with the stones. On each turn, we choose the h**eaviest two stones** and smash them together. Suppose the heaviest two stones have weights ```x``` and ```y``` with ```x <= y```. The result of this smash is:

* If ```x == y```, both stones are destroyed, and
* If ```x != y```, the stone of weight ```x``` is destroyed, and the stone of weight ```y``` has new weight ```y - x```.

At the end of the game, there is **at most one** stone left.

Return the weight of the last remaining stone. If there are no stones left, return ```0```.

## 解題想法:
* 題目為，給一數組，每次選出最大的兩數比較
* 若相等，皆刪除
* 否則，(大-小)放回數組
* 繼續比較
* 最終若數組還有剩，return剩的那個，否則return 0

* 使用heap裝取所有數
* 每次heappop()在將大於0的差值heappush即可

## Python:
* **heapq**: 為min_heap

from heapq import heappush, heappop
class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        que=[]
        #加上負號讓大的變最小可以先被heappop
        for i in stones:
            heappush(que,-i)
        while len(que)>=2:
            first=-heappop(que)
            second=-heappop(que)
            diff=first-second
            if diff>0:
                heappush(que,-diff)
        return -que[0] if que else 0

## C++:
* include < queue > :
* **priority_queue** < int > 優先隊列:
* 為max_que: 大的會先被pop

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        //#include<queue>
        priority_queue<int> que;
        for (auto val: stones)
            que.push(val);
        
        while (que.size()>=2){
            int first=que.top(); que.pop();
            int second=que.top(); que.pop();
            if (first-second>0)
                que.push(first-second);
        }
        return (!que.empty())? que.top() : 0;
    }
};