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 [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
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.

題目翻譯

給定一個整數陣列 stones，每個元素紀錄的是每個石頭的重量。現在我們會找出兩個最重的石頭互相撞擊，如果兩個重量相同就會兩個都消失；如果一大一小則小的會消失，大的會變成剩下 x-y 的重量。這題就是要一直互相撞擊，留下最後一個石頭。要找出其重量

解法解析

這題可以用 Sorted array 或是用 Max Heap，看到最多人使用這兩種方式。因為其寫法簡單且直覺，但是其時間複雜度相對的高，因為是每次比對完之後都要重新做一次排序。

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[0] 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

我最後範例的解法則是使用了 Bucket sort，雖然第一眼沒有那麼好懂，但是時間複雜度是最低的。解法的概念是，將各個值放到各字對映的陣列索引上，然後紀錄該值有幾個 [2, 7, 4, 1, 8, 1] => [0, 2, 1, 0, 1, 0, 0, 1, 1]。然後從尾巴最大值開始向開頭比對。

解法範例

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[0]
    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 = [0] * (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