最小区间

最小区间

三月 07, 2022

最小区间

这道题在参考题解以后最后决定用这种方式解决

alt

我们构造k个元素的堆（相当于指针了 再构造一个储存序列的数组

然后每个列表中从最小值开始遍历，（因为符合题意的最优解肯定是拥有每个列表中一个元素）然后让最小值序列+1 逐次遍历 计算堆中最大值和最小值的差 最后得到最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k = len(nums)
        if k==1: return [nums[0][0],nums[0][0]]
        indexs = [0]*k
        lists = []
        largest = -10**5
        import heapq
        # 生成大小为k的堆
        for i in range(k):
            num = nums[i][0]
            heapq.heappush(lists,(num,i))
            largest = max(largest,num)

        left,right = lists[0][0],largest

        while True:
            num,i = heapq.heappop(lists)
            # 取出最小的数，以及对应的列表的下标
            indexs[i] += 1
            # 下标+1
            if indexs[i] >= len(nums[i]): # 退出循环
                break
            # 通过下标i找到列表，再通过indexs数组找到下一个元素的下标
            newnum = nums[i][indexs[i]]
            heapq.heappush(lists,(newnum,i)) #插入新的数
            largest = max(largest,newnum) # 更新最大值
            if largest-lists[0][0]<right-left: #更新区间
                left, right = lists[0][0], largest
        return [left,right]

alt