Problem Description
1046. Last Stone Weight
Description
Do as the game. Choose two heaviest stone and do the subtraction.
Use Priority Queue to easily find the two heaviest stone.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq(stones.begin(), stones.end());
while(pq.size() > 1) {
int x = pq.top();
pq.pop();
int y = pq.top();
pq.pop();
if(x != y) {
pq.push(x - y);
}
}
if(pq.empty()) return 0;
return pq.top();
}
};
|
Author: o_oyao
License: All articles in this blog are licensed under
CC BY-NC-SA 4.0 unless stating additionally.
