632. Smallest Range Covering Elements from K Lists ## 思路 類似merge k list 先把k個list都加到heap (arr[0], i, 0) 再逐次pop出來(curr_min) 如果第i個list還有值就push進來並更新curr_max ## Code ```python class Solution: def smallestRange(self, nums: List[List[int]]) -> List[int]: heap = [(arr[0], idx, 0) for idx, arr in enumerate(nums)] heapq.heapify(heap) range_min, range_max = float('-inf'), float('inf') curr_max = max(arr[0] for arr in nums) while heap: curr_min, i, j = heapq.heappop(heap) if curr_max - curr_min < range_max - range_min: range_min, range_max = curr_min, curr_max if j == len(nums[i])-1: break curr_max = max(curr_max, nums[i][j+1]) heapq.heappush(heap, (nums[i][j+1], i, j+1)) return [range_min, range_max] ``` -- https://i.imgur.com/kyBhy6o.jpeg -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.111 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728783507.A.190.html