632. 最小区间

Difficulty
Hard
Tags
滑动窗口
URL
https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
Star
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：
输出：[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
  • 105 <= nums[i][j] <= 105
  • nums[i] 按非递减顺序排列
通过次数21,529提交次数35,731
 

滑动窗口

思路
将nums中k个数组合并成一个数组，对每个数字记录其所在的数组编号和值。定义Pair类来表示合并后的元素，Pair.num表示该元素的值；Pair.idx表示该元素所在的原数组编号。
将k个数组合并成一个之后就可以将问题简化成：求一个最小区间，使得该区间满足 区间中包含的元素中至少有一个在原数组i中，i属于[1,k]。可以使用滑动窗口求解。
这样就将问题转化到
📷
3. 无重复字符的最长子串 题，窗口内的数据类型要求是k
题解
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        
        # 将原数组转化我 [[num, idx], []] 的形式， num就是值，idx是在原数组的位置
        arr = []
        for i in range(0, len(nums)):
            for j in range(0, len(nums[i])):
                arr.append([nums[i][j], i])

        arr.sort()
        
        res = [arr[0][1], arr[-1][0]]
        l, r = 0, 0
        wds = collections.defaultdict(int)

        while r < len(arr):
            wds[arr[r][1]] += 1
            # 该窗口的内的 数据 要包括所有
            while len(wds) == len(nums):
                if arr[r][0] - arr[l][0] < res[1]-res[0] or arr[l][0] < res[0]:
                    res = [arr[l][0], arr[r][0]]

                wds[arr[l][1]] -= 1
                if wds[arr[l][1]] == 0:
                    del wds[arr[l][1]]

                l += 1

            r += 1

        return res