632. 最小区间

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1:

输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

注意:

  1. 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
  2. 1 <= k <= 3500
  3. -10 <= 元素的值 <= 10
  4. 对于使用Java的用户，请注意传入类型已修改为List>。重置代码模板后可以看到这项改动。

    方法：K-pointer

    思路

  • 用k个指针来表示指向k个list中的元素，计算此时的最大最小值
  • 此时的range与全局的最大最小值形成的range进行比较
  • 如果此时range更小，那么更新全局的最大最小值

  • 不断右移指针，直到有指针到达最后一个元素

    实现

  • index_list，长度为k的数组，记录指针位置

  • elem_list，长度为k的数组，记录指针指向的元素值
  • currmaxval, currminval，此时elem_list中的最大最小值

  • maxval, minval，全局的最大最小值

    代码

    1. class Solution:
    2.   def smallestRange(self, nums: List[List[int]]) -> List[int]:
    3.       # define variables
    4.       k = len(nums)
    5.       index_list = [0] * k
    6.       elem_list = [0] * k
    7.       for i in range(k):
    8.           elem_list[i] = nums[i][index_list[i]]
    9.       minval, maxval = min(elem_list), max(elem_list)
    11.       # recursion
    12.       while True:
    13.           currminval, currmaxval = min(elem_list), max(elem_list)
    14.           if currmaxval - currminval < maxval - minval:
    15.               maxval = currmaxval
    16.               minval = currminval
    17.           index = elem_list.index(currminval)
    18.           if index_list[index] < len(nums[index]) - 1:
    19.               index_list[index] += 1
    20.               elem_list[index] = nums[index][index_list[index]]
    21.           else:
    22.               break
    23.       return [minval, maxval]