# 1046. Last Stone Weight

## 題目敘述

You are given an array of integers `stones` where `stones[i]` is the weight of the `i**th` stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights `x` and `y` with `x <= y`. The result of this smash is:

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

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return `0`.

Example 1:

``````Input: stones = [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  then that's the value of the last stone.
``````

Example 2:

``````Input: stones = 
Output: 1
``````

Constraints:

• `1 <= stones.length <= 30`
• `1 <= stones[i] <= 1000`

Hint 1:

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

## 解法解析

### Sorted array

``````class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
while len(stones) > 1:
stone_1 = stones.pop()
stone_2 = stones.pop()
if stone_1 != stone_2:
bisect.insort(stones, stone_1 - stone_2)
return stones if stones else 0
``````

### Heap

``````class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:

# Make all the stones negative. We want to do this *in place*, to keep the
# space complexity of this algorithm at O(1). :-)
for i in range(len(stones)):
stones[i] *= -1

# Heapify all the stones.
heapq.heapify(stones)

# While there is more than one stone left, remove the two
# largest, smash them together, and insert the result
# back into the heap if it is non-zero.
while len(stones) > 1:
stone_1 = heapq.heappop(stones)
stone_2 = heapq.heappop(stones)
if stone_1 != stone_2:
heapq.heappush(stones, stone_1 - stone_2)

# Check if there is a stone left to return. Convert it back
# to positive.
return -heapq.heappop(stones) if stones else 0
``````

### 解法範例

#### Go

``````func lastStoneWeight(stones []int) int {
maxWeight := max(stones)
buckets := make([]int, maxWeight+1)

for _, value := range stones {
buckets[value]++
}

biggestWeight := 0
currentWeight := maxWeight
for currentWeight > 0 {
if buckets[currentWeight] == 0 {
currentWeight--
} else if biggestWeight == 0 {
buckets[currentWeight] %= 2
if buckets[currentWeight] == 1 {
biggestWeight = currentWeight
}
currentWeight--
} else {
buckets[currentWeight]--
if biggestWeight-currentWeight <= currentWeight {
buckets[biggestWeight-currentWeight]++
biggestWeight = 0
} else {
biggestWeight -= currentWeight
}
}
}

return biggestWeight
}

func max(stones []int) (max int) {
max_one := stones
for _, value := range stones {
if value > max_one {
max_one = value
}
}
return max_one
}
``````

#### JavaScript

``````/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeight = function (stones) {
const maxWeight = Math.max(...stones);
const buckets = new Array(maxWeight + 1).fill(0);
for (const weight of stones) {
buckets[weight]++;
}

let biggestWeight = 0,
currentWeight = maxWeight;
while (currentWeight > 0) {
if (buckets[currentWeight] === 0) {
currentWeight--;
} else if (biggestWeight === 0) {
buckets[currentWeight] %= 2;
if (buckets[currentWeight] === 1) {
biggestWeight = currentWeight;
}
currentWeight--;
} else {
buckets[currentWeight]--;
if (biggestWeight - currentWeight <= currentWeight) {
buckets[biggestWeight - currentWeight]++;
biggestWeight = 0;
} else {
biggestWeight -= currentWeight;
}
}
}
return biggestWeight;
};
``````

#### Kotlin

``````
``````

#### PHP

``````class Solution
{

/**
* @param Integer[] \$stones
* @return Integer
*/
function lastStoneWeight(\$stones)
{
\$maxWeight = max(\$stones);
\$buckets = array_fill(0, \$maxWeight + 1, 0);
foreach (\$stones as \$stone) {
\$buckets[\$stone]++;
}

\$biggestWeight = 0;
\$currentWeight = \$maxWeight;
while (\$currentWeight > 0) {
if (\$buckets[\$currentWeight] == 0) {
\$currentWeight--;
} else if (\$biggestWeight == 0) {
\$buckets[\$currentWeight] %= 2;
if (\$buckets[\$currentWeight] == 1) {
\$biggestWeight = \$currentWeight;
}
\$currentWeight--;
} else {
\$buckets[\$currentWeight]--;
if (\$biggestWeight - \$currentWeight <= \$currentWeight) {
\$buckets[\$biggestWeight - \$currentWeight]++;
\$biggestWeight = 0;
} else {
\$biggestWeight -= \$currentWeight;
}
}
}
return \$biggestWeight;
}
}
``````

#### Python

``````class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:

# Set up the bucket array.
max_weight = max(stones)
buckets =  * (max_weight + 1)

# Bucket sort.
for weight in stones:
buckets[weight] += 1

# Scan through the weights.
biggest_weight = 0
current_weight = max_weight
while current_weight > 0:
if buckets[current_weight] == 0:
current_weight -= 1
elif biggest_weight == 0:
buckets[current_weight] %= 2
if buckets[current_weight] == 1:
biggest_weight = current_weight
current_weight -= 1
else:
buckets[current_weight] -= 1
if biggest_weight - current_weight <= current_weight:
buckets[biggest_weight - current_weight] += 1
biggest_weight = 0
else:
biggest_weight -= current_weight
return biggest_weight
``````

#### Rust

``````
``````

#### Swift

``````
``````