分析
每次都拿最重的两个,想到可以使用优先队列进行处理,当优先队列最后的大小为1时,堆顶元素就是答案。
C++ 代码
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
int n=stones.size();
priority_queue<int> heap; //建立优先队列
if(n<1) return 0;
for(int i=0;i<n;i++) heap.push(stones[i]);
while(heap.size()>1)
{
auto y=heap.top(); //拿出两个元素
heap.pop();
auto x=heap.top();
heap.pop();
heap.push(abs(y-x));
}
return heap.top();
}
};