1046. Last Stone Weight

by

1046. Last Stone Weight

Easy

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

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

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

思路

（略）

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> max_heap;
        for (auto stone : stones) {
            max_heap.push(stone);
        }
        
        while (max_heap.size() > 1) {
            auto stone_1 = max_heap.top();
            max_heap.pop();
            auto stone_2 = max_heap.top();
            max_heap.pop();
            if (stone_1 == stone_2) {
                continue;
            } else {
                max_heap.push(stone_1 < stone_2 ? stone_2 - stone_1 : stone_1 - stone_2);
            }
        }
        if (max_heap.empty()) {
            return 0;
        }
        else {
            return max_heap.top();
        }
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Last Stone Weight.

Memory Usage: 7.5 MB, less than 76.97% of C++ online submissions for Last Stone Weight.

Leave a Comment