千问 LeetCode 3049. 标记所有下标的最早秒数 II Python3实现

以下是 LeetCode 3049. 标记所有下标的最早秒数 II 的 Python3 实现。核心思路回顾1. 二分查找对时间进行二分判断在 mid 秒内能否完成所有下标的标记。2. 反悔贪心倒序遍历时间线。对于某个下标 i 的首次出现且 nums[i] 1我们优先尝试“直接置零”消耗1秒。如果当前空闲时间不够我们检查堆顶元素之前选择直接置零的元素中代价最小的如果当前元素的值更大则“反悔”撤销堆顶元素的直接置零改为逐步递减归还时间转而将当前元素直接置零。3. 最终判定遍历结束后判断剩余的空闲时间是否大于等于剩余需要逐步递减的总代价。Python3 代码实现import heapqfrom typing import Listclass Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) - int:n, m len(nums), len(changeIndices)# 计算理论上的最大耗时所有元素逐步递减的总和 n个标记操作tot sum(nums) n# 预处理记录每个下标在 changeIndices 中最早出现的位置first [-1] * nfor i in range(m - 1, -1, -1):first[changeIndices[i] - 1] i # 转为0-indexed# 二分查找最早秒数l, r n, m 1while l r:mid (l r) 1if self._check(nums, changeIndices, first, mid, tot):r midelse:l mid 1return r if r m else -1def _check(self, nums: List[int], tag: List[int], first: List[int], lim: int, tot: int) - bool:res 0 # 当前可用的空闲时间s tot # 还需要通过“逐步递减”或“直接置零”消耗的总代价pq [] # 小根堆用于反悔贪心存储已经选择“直接置零”的元素的值# 倒序遍历前 lim 秒for i in range(lim - 1, -1, -1):id_ tag[i] - 1 # 转为0-indexedx nums[id_]# 如果不是首次出现或者值1直接作为空闲时间if x 1 or i ! first[id_]:res 1continue# 如果是首次出现且 x 1考虑是否进行“直接置零”操作if res 0:# 如果没有空闲时间尝试反悔if pq and x pq[0]:# 反悔撤销堆顶元素的直接置零改为逐步递减s heapq.heappop(pq) 1res 2 # 归还1秒置零时间 1秒标记时间else:# 无法反悔或当前元素不值得反悔当前秒作为空闲时间res 1continue# 对当前元素执行“直接置零”操作s - (x 1) # 扣除直接置零和标记的代价heapq.heappush(pq, x) # 记录到堆中以便未来可能被反悔res - 1 # 消耗1秒进行置零操作# 判断剩余的空闲时间是否足以完成所有剩余的“逐步递减”操作return res s复杂度分析- 时间复杂度O(m log m)。二分查找需要 O(log m) 次迭代每次 _check 函数内部倒序遍历并配合优先队列堆操作需要 O(m log m) 的时间。- 空间复杂度O(m)。主要用于存储 first 数组和优先队列。