【剑斩OFFER】算法的暴力美学——力扣 1046 题：最后一块石头的重量

一、题目描述

二、算法原理

思路：大根堆

把所有的数据入堆，然后依次拿取堆顶元素，判断这个两个元素是否相等，不相等，大的值减去小的值入堆；当堆只有一个元素或者没有数据时，就结束循环，最终如果这个堆有数据那么这个数据就是最终答案，否则返回 0

三、代码实现

class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> maxpq;//大堆 for(auto& e : stones) maxpq.push(e); while(!maxpq.empty() && maxpq.size() != 1) { int x = maxpq.top();//获取堆顶元素 maxpq.pop();//出堆 int y = maxpq.top(); maxpq.pop(); if(x != y) maxpq.push(x - y);//入堆 } if(maxpq.empty()) return 0; return maxpq.top(); } };