動機
就heap
Problem
You have k
lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k
lists.
We define the range [a, b]
is smaller than range [c, d]
if b - a < d - c
or a < c
if b - a == d - c
.
Example 1:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]Output: [20,24]Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24].List 2: [0, 9, 12, 20], 20 is in range [20,24].List 3: [5, 18, 22, 30], 22 is in range [20,24].
Example 2:
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]Output: [1,1]
Example 3:
Input: nums = [[10,10],[11,11]]Output: [10,11]
Example 4:
Input: nums = [[10],[11]]Output: [10,11]
Example 5:
Input: nums = [[1],[2],[3],[4],[5],[6],[7]]Output: [1,7]
Constraints:
nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i]
is sorted in non-decreasing order.
Sol
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
hq, big = [], float('-inf')
def add(l,i):
nonlocal big
heappush(hq,(l[0],i))
big = max(big,l[0])
nums = [deque(l) for l in nums]
[add(l,i) for (i,l) in enumerate(nums)]
ret = [hq[0][0],big]
while len(hq) == len(nums):
_, i = heappop(hq)
nums[i].popleft()
#[print(l) for l in nums]
#print("=====")
if nums[i]:
add(nums[i],i)
ret = min([ret,[hq[0][0],big]], key=lambda x: x[1]-x[0])
return ret