The Weight of the Last Stone#

There is a pile of stones, and the weight of each stone is a positive integer.

In each round, the heaviest two stones are selected from the pile and smashed together. Let's assume the weights of the stones are x and y, and x <= y. The possible results of the smashing are as follows:

• If x == y, both stones will be completely smashed.
• If x != y, the stone with weight x will be completely smashed, and the stone with weight y will have a new weight of y-x.

In the end, there will be at most one stone left. Return the weight of this stone. If there are no stones left, return 0.

Example#

Input: [2,7,4,1,8,1]
Output: 1
Explanation:
- Select 7 and 8 first, the remaining array is [2,4,1,1,1]
- Then select 2 and 4, the remaining array is [2,1,1,1]
- Next, 2 and 1 are selected, the remaining array is [1,1,1]
- Finally, 1 and 1 are selected, and the remaining array is [1]
- The weight of the last stone left is 1.

Approach#

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    const findMax = function(arr){
        let index = 0;
        let max = ~~arr[0];
        arr.forEach((v,i) => {
            if(v > max) {
                index = i;
                max = v;
            }
        })
        return [index, max];
    }

    if(stones.length === 0) return 0;
    if(stones.length === 1) return stones[0];
    while(stones.length > 1) {
        let [yIndex, y] = findMax(stones);
        stones.splice(yIndex, 1); 
        let [xIndex, x] = findMax(stones);
        stones.splice(xIndex, 1); 
        if (x !== y) stones.push(y-x);
    }
    return stones.length === 1 ? stones[0] : 0;
};

Idea#

Simply simulate the process as required in the problem. Each time, select the two heaviest stones, then check their weights. If they are different, put the difference back into the array. It's also possible to solve the problem using a priority queue, but in the solution provided, a function was implemented to find the maximum value and its index. This was necessary because using Math.max() alone does not provide the index, and the index is needed to remove the value. Firstly, a function was defined to find the maximum value and its index, with the index set to 0 and the maximum value set to the first element of the array. If the array is empty, this will convert undefined to 0. Then, the array is looped through to record the index and value if the value in the array is greater than the defined max value. Finally, the index and max value are returned. Then, the length of the array is checked. If the length is 0, 0 is returned. If it is 1, the value is returned. Then a loop is defined. The loop condition is that the array length is greater than or equal to two. The current maximum value and its index are obtained, and then this value is removed from the array. Then the current maximum value and its index are obtained, and then this value is removed from the array. If the two maximum values are not the same, the difference is put back into the array. Finally, if the length of the array is 1, the value is returned, otherwise 0 is returned.

Daily Topic#

Reference#