LeetCode Entry

1962. Remove Stones to Minimize the Total

28.12.2022 medium 2022 kotlin

fun minStoneSum(piles: IntArray, k: Int): Int {

1962. Remove Stones to Minimize the Total medium

https://t.me/leetcode_daily_unstoppable/66

blog post

    fun minStoneSum(piles: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>()
        var sum = 0
        piles.forEach {
            sum += it
            pq.add(-it)
        }
        for (i in 1..k) {
            if (pq.isEmpty()) break
            val max = -pq.poll()
            if (max == 0) break
            val newVal = Math.round(max/2.0).toInt()
            sum -= max - newVal
            pq.add(-newVal)
        }
        return sum
    }

By the problem definition, intuitively the best strategy is to reduce the maximum each time. Use PriorityQueue to keep track of the maximum value and update it dynamically.

• one can use variable sum and update it each time.

Space: O(n), Time: O(nlogn)