1046. Last Stone Weight.md

1046. Last Stone Weight

---

leetcode-cn Daily Challenge on December 30th, 2020.

---

Difficulty : Easy

Related Topics : Heap、Greedy

---

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

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

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [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 last stone.

Note:

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

---

Solution

• mine
  • Java

    • Sort Runtime: 1 ms, faster than 83.04%, Memory Usage: 36.5 MB, less than 30.04% of Java online submissions

      public int lastStoneWeight(int[] stones) {
          List<Integer> list = new ArrayList<>(stones.length);
          for(int s : stones) list.add(s);
          while(list.size() > 1){
              Collections.sort(list);
              int a = list.remove(list.size() - 1);
              int b = list.remove(list.size() - 1);
              if(a != b){
                  a -= b;
                  list.add(a);
              }
          }
          return list.size() == 0 ? 0 : list.get(0);
      }
      

    • Heap Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.4 MB, less than 66.00% of Java online submissions

      public int lastStoneWeight(int[] stones) {
          int n = stones.length;
          buildHeap(stones, n);
          while(n > 1){
              int a = stones[0];
              swap(stones, 0, n - 1);
              heapify(stones, 0, n - 1);
              int b = stones[0];
              swap(stones, 0, n - 2);
              heapify(stones, 0, n - 2);
              n -= 2;
              if(a != b){
                  a -= b;
                  stones[n++] = a;
                  buildHeap(stones, n);
              }
          }
          return n == 0 ? 0 : stones[0];
      }
      
      void buildHeap(int[] arr, int n){
          for(int i = n / 2; i >= 0; i--){
              heapify(arr, i, n);
          }
      }
      
      void heapify(int[] arr, int i, int n){
          int l = i * 2 + 1;
          int r = i * 2 + 2;
          int max = i;
          if(r < n){
              if(arr[r] > arr[max]) max = r;
          }
          if(l < n){
              if(arr[l] > arr[max]) max = l;
          }
          if(max != i) {
              swap(arr, i, max);
              heapify(arr, max, n);
          }
      }
      
      void swap(int[] arr, int a, int b){
          int x = arr[a];
          arr[a] = arr[b];
          arr[b] = x;
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 36 MB, less than 97.08% of Java online submissions

  public int lastStoneWeight(int[] stones) {
      if (stones.length == 1) {
          return stones[0];
      }
      Arrays.sort(stones);
      while (stones[stones.length - 2] != 0) {
          stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2];
          stones[stones.length - 2] = 0;
          Arrays.sort(stones);
      }
      return stones[stones.length - 1];
  }
  

---