（算法）最后⼀块⽯头的重量————＜堆＞

1. 题⽬链接：1046.最后⼀块⽯头的重量

2. 题⽬描述：

3. 解法（利⽤堆）：

算法思路：

其实就是⼀个模拟的过程：

• 每次从⽯堆中拿出最⼤的元素以及次⼤的元素，然后将它们粉碎；

• 如果还有剩余，就将剩余的⽯头继续放在原始的⽯堆⾥⾯重复上⾯的操作，直到⽯堆⾥⾯只剩下⼀个元素，或者没有元素（因为所有的⽯头可能全部抵消了）

那么主要的问题就是解决：

• 如何顺利的拿出最⼤的⽯头以及次⼤的⽯头；

• 并且将粉碎后的⽯头放⼊⽯堆中之后，也能快速找到下⼀轮粉碎的最⼤⽯头和次⼤⽯头； 这不正好可以利⽤堆的特性来实现嘛？

• 我们可以创建⼀个⼤根堆；

• 然后将所有的⽯头放⼊⼤根堆中；

• 每次拿出前两个堆顶元素粉碎⼀下，如果还有剩余，就将剩余的⽯头继续放⼊堆中；

这样就能快速的模拟出这个过程。 

C++算法代码： 

class Solution 
{
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        //创建一个大根堆
        priority_queue<int> heap;
        //将所有元素放入大根堆
        for(int temp:stones)
        {
            heap.push(temp);
        }
        while(heap.size()>1)
        {
            //取出两个最大元素
            int a=heap.top();
            heap.pop();
            int b=heap.top();
            heap.pop();
            if(a>b)
            {
                heap.push(a-b);
            }
        }
        //当堆中有元素时返回元素，没有元素时返回0
        return heap.size()?heap.top():0;
    }
};

Java算法代码：

class Solution
{
	public int lastStoneWeight(int[] stones)
	{
		// 1. 创建⼀个⼤根堆 
		PriorityQueue<Integer> heap = new PriorityQueue<>((a, b)->b - a);
		// 2. 把所有的⽯头放进堆⾥⾯ 
		for (int x : stones)
		{
			heap.offer(x);
		}
		// 3. 模拟 
		while (heap.size() > 1)
		{
			int a = heap.poll();
			int b = heap.poll();
			if (a > b)
			{
				heap.offer(a - b);
			}
		}
		return heap.isEmpty() ? 0 : heap.peek();
	}
}