1046.Last Stone Weight
===

###### tags: `Easy`,`Array`,`Heap`

[1046. Last Stone Weight](https://leetcode.com/problems/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 new weight `y - x`.

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

Return *the weight of the last remaining 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

### 解答
#### Python

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Max heap = Negative min heap
        stones = [-stone for stone in stones]
        heapq.heapify(stones)

        while len(stones) > 1:
            x, y = heapq.heappop(stones), heapq.heappop(stones)
            if x != y:
                heapq.heappush(stones, x - y)

        return -heapq.heappop(stones) if stones else 0

> [name=Ron Chen][time=Mon, Apr 24, 2023]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        self.heap = []
        def swap(i, j):
            tmp = self.heap[i]
            self.heap[i] = self.heap[j]
            self.heap[j] = tmp
        def insert(value):
            self.heap.append(value)
            k = len(self.heap) - 1
            while k > 0 and self.heap[k] > self.heap[(k-1)//2]:
                swap(k, (k-1)//2)
                k = (k-1)//2
        def pop():
            value = self.heap[0]
            self.heap[0] = self.heap[-1]
            self.heap.pop()
            k = 0
            while k * 2 + 1 < len(self.heap):
                j = k * 2 + 1
                if k * 2 + 2 < len(self.heap) and self.heap[k*2+2] > self.heap[k*2+1]:
                    j = k * 2 + 2
                if self.heap[j] > self.heap[k]:
                    swap(j, k)
                k = j
            return value

        for s in stones:
            insert(s)

        while len(self.heap) > 1:
            s1 = pop()
            s2 = pop()
            ret = abs(s1-s2)
            if ret > 0:
                insert(ret)
        if len(self.heap) > 0:
            return self.heap[0]
        else:
            return 0

> [name=gpwork4u][time=Mon, Apr 24, 2023]

#### Javascript

function lastStoneWeight(stones) {
  const heap = new MaxHeap();
  for (const stone of stones) {
    heap.push(stone);
  }

  while (heap.queue.length > 1) {
    const max = heap.pop();
    const second = heap.pop();
    if (max !== second) heap.push(max - second);
  }

  return heap.queue.length === 0 ? 0 : heap.pop();
}

> 寫這題才發現我上次寫的maxheap有bug...趕緊改一下
> 用JS刷題貌似真的不太適合
> [name=Marsgoat][time=Mon, Apr 24, 2023]

#### TypeScript

function lastStoneWeight(stones: number[]): number {
  if (stones.length === 0) return 0;
  if (stones.length === 1) return stones[0];

  const sortedList: number[] = [...stones].sort((a, b) => b - a);
  const smashedResult = sortedList[0] - sortedList[1];

  if (smashedResult > 0) {
    sortedList.splice(0, 2, smashedResult);
  } else {
    sortedList.splice(0, 2);
  }

  return lastStoneWeight(sortedList);
}

> 不會 heap 直接爆破
> [name=Sheep][time=Mon, Apr 24, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)