1046_last_stone_weight.rb

# Leetcode problem: https://leetcode.com/problems/last-stone-weight/
#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
# ----------------------------------------------------------------------------------------------------------------------
# @param {Integer[]} stones
# @return {Integer}
require_relative 'core/heap'
def last_stone_weight(stones)
  max_heap = Heap.new :>

  stones.each do |stone|
    max_heap.add stone
  end

  until max_heap.empty?
    element_biggest = max_heap.pop
    element_bigger = max_heap.pop

    return element_biggest if element_bigger.nil?

    difference_after_smash = element_biggest - element_bigger
    max_heap.add difference_after_smash
  end

  0
end

p last_stone_weight [2, 7, 4, 1, 8, 1]