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 <= stones.length <= 30
1 <= stones[i] <= 1000

Hints:
Simulate the process. We can do it with a heap, or by sorting some list of stones every time we take a turn.

What is a Priority Queue?

We know a Queue is a First In First Out data structure. The Priority Queue is a special queue that the max or min value of the queue is popped out (dequeue). Therefore, the Priority Queue is usually based on a max/min heap.

Priority Queue in C++ Example

Be default, the priority queue in C++ pops out the max element. Thus the above problem can be solved by simulating the process using a priority queue. Popping out two elements which are the biggest in the array, and push the difference (if it is not zero) back to the priority queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if (stones.empty()) return 0;
        priority_queue<int> pq;
        for (const auto &n: stones) {
            pq.push(n);
        }
        while (pq.size() > 1) {
            int s1 = pq.top();
            pq.pop();
            int s2 = pq.top();
            pq.pop();
            if (s1 != s2) pq.push(s1 - s2);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if (stones.empty()) return 0;
        priority_queue<int> pq;
        for (const auto &n: stones) {
            pq.push(n);
        }
        while (pq.size() > 1) {
            int s1 = pq.top();
            pq.pop();
            int s2 = pq.top();
            pq.pop();
            if (s1 != s2) pq.push(s1 - s2);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

We can declare in C++ a min priority queue, using the following syntax:

1

priority_queue<int, vector<int>, std::greater<int>> pq;

priority_queue<int, vector<int>, std::greater<int>> pq;

Priority Queue in Java Example

In Java, we can instantise the abstract Queue type using Priority Queue. By default, the Priority Queue in Java pops out the min element, and thus, we would need to provide the custom comparator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int lastStoneWeight(int[] stones) {
        Queue<Integer> pq = new PriorityQueue<Integer>(stones.length, (a, b) -> b - a);
        for (int x: stones) {
            pq.offer(x);
        }
        while (pq.size() > 1) {
            int a = pq.peek();
            pq.poll();
            int b = pq.peek();
            pq.poll();
            if (a != b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

class Solution {
    public int lastStoneWeight(int[] stones) {
        Queue<Integer> pq = new PriorityQueue<Integer>(stones.length, (a, b) -> b - a);
        for (int x: stones) {
            pq.offer(x);
        }
        while (pq.size() > 1) {
            int a = pq.peek();
            pq.poll();
            int b = pq.peek();
            pq.poll();
            if (a != b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

The Priority Queue overloaded constructor takes first parameter as the initial capacity.

–EOF (The Ultimate Computing & Technology Blog) —