今日题目

https://leetcode.com/problems/minimum-operations-to-exceed-threshold-value-ii/description

解题思路

用堆模拟题目要求的操作。

解题方法

  1. 使用堆取出列表中最小的两个数。
  2. 将 $2 * min(x, y) + max(x, y)$ 的结果重新放入堆中。
  3. 若取出的值均大于等于 k，则操作完成。

复杂度分析

  • 时间复杂度：$O(N\times log(N))$，N 为序列长度。

  • 空间复杂度：$O(1)$，使用 heapify 原地建堆，无需额外存储空间。

代码

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        ans = 0
        heapify(nums)
        x = heappop(nums)
        while(len(nums) > 0 and x < k):
            y = heappop(nums)
            nx = min(x, y) * 2 + max(x, y)
            heappush(nums, nx)
            x = heappop(nums)
            ans += 1
        
        return ans