0632：最小区间（★★）

2016-09-23 约 355 字预计阅读 1 分钟次阅读

力扣第 632 题

题目

你有 k 个 非递减排列 的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[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] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] 按非递减顺序排列

相似问题：

0076：最小覆盖子串

分析

枚举每个数作为区间右边界，找最大的左边界，可以用滑动窗口解决。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k = len(nums)
        A = sorted((a,x) for x,arr in enumerate(nums) for a in arr)
        res, i = [-inf,inf], 0
        ct = defaultdict(int)
        for a,x in A:
            ct[x]+=1
            while len(ct)==k:
                b, y = A[i]
                if a-b<res[1]-res[0]:
                    res = [b,a]
                ct[y] -= 1
                if not ct[y]:
                    del ct[y]
                i += 1
        return res

100 ms

目录

0632：最小区间（★★）

题目

分析

解答