Last Stone Weight
Repeatedly smash the two heaviest stones. Equal stones both disappear; otherwise their positive weight difference is returned. Find the final weight.
Work through the cases
3 examplesInput notation
Positive stone weights separated by spaces.Expected result
The remaining weight, or 0.Case 1
Input
2 7 4 1 8 1
Expected output
1
Case 2
Input
5 5
Expected output
0
Case 3
Input
9
Expected output
9
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Each smash uses the two heaviest stones. Scanning for the maximum every time repeats comparisons; a heap extracts them in logarithmic time. Negating the weights turns a min-heap into a max-heap. Pop y ≥ x and push y-x when they differ, until fewer than two stones remain. An empty heap is 0; otherwise the answer is the negated top.
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
for (int x : stones) {
q.offer(x);
}
while (q.size() > 1) {
int y = q.poll();
int x = q.poll();
if (x != y) {
q.offer(y - x);
}
}
return q.isEmpty() ? 0 : q.poll();
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.