632. 最小区间 [hard]

https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/

你有 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 <= k <= 3500
-105 <= 元素的值 <= 105
对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。

通过次数10,229 | 提交次数18,392

First Try

2020-08-01

还是得看题解, 这个解法确实比之前failed try里讨巧的解法在逻辑上要来得扎实.

假设已经成功选择了最小区间，这个最小区间的左边界元素minv在列表a上，那么其他列表中被选中在这个最小区间里的元素，肯定是刚好比a中的minv大一点的元素。原因:

a中的minv已经是最小区间中的左边界元素，也即最小元素。
如果在b列表中存在大于minv的元素p和q，并且p<q, 如果选择[a, q],那么[a, q] > [a, p]并不是最小区间，因此必然选择p。

既然是刚好比a大一点的元素，那么按照合并k个有序数组的写法，按照最小堆来排序，不断剔除最小的元素，刚好剔除到a中的minv元素时，队列里剩下的列表的第一个元素就都是这个最小区间中。

剩下的问题是如何确定最小区间的最小元素就是a中的minv？答案是并没法直接确定，完全是靠遍历的方法来暴力穷举，只是穷举的比较有技巧，仅仅是O(N)复杂度。

每次从有限队列里出来的第一个元素，都被当作minv元素，然后与当前这一轮里的最大值进行比较，记录下gap数值和边界数值。当最后有一个数组即将消失的时候，之前最小的gap数值所代表的左边界和右边界就是答案。

如何快速得到每一轮的maxv的数值也有小技巧，看代码就知道了。

# 还是得看题解
# 这个解法确实比之前得讨巧解法在逻辑上要来得扎实
import heapq 

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heapq.heapify(nums)
        maxv = max(nums)[0]
        lft, rt = float('-inf'), float('inf')
        while len(nums):
            seq = heapq.heappop(nums)
            minv = seq.pop(0)  # 选择这个当被选中得最小值试下
            if maxv - minv < rt - lft:
                lft, rt = minv, maxv 
            if len(seq) == 0:
                return [lft, rt]
            maxv = max(maxv, seq[0]) # seq得第二个元素可能是下一轮的最大，也可能不是
            heapq.heappush(nums, seq)

执行用时：296 ms, 在所有 Python3 提交中击败了74.38%的用户
内存消耗：18.1 MB, 在所有 Python3 提交中击败了100.00%的用户

Failed Try

2020-08-01

以为是按照k路有序数组合并的思路，猜测当合并到某个数组即将消失的时候，接下来的元素都在最小区间内。有几个test case答对了，但是遇到相同的数组的时候又悲剧。

考虑是否应该将最小堆改为最大堆？然后一顿改，发现相同数组答对了，但其他的答案又错了。

考虑是否应该同时考虑最小堆和最大堆？同时处理一遍，得到两个结果，然后对两个结果进行比较选出最小区间。结果在一些test case上又挂掉了。

归根结底，这种思路只是模糊觉得应该这样，并没有像first try里面用反证法严格说明应该如何做。

但要在有限时间里想出first try里的思路，还是得多了解套路才行。

要不正反个来一遍，然后比较下？

import heapq

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # 看评论得到的思路，k路归并，看到这几个字就思路了。。。
        # 从第一个快被消灭的元素中获取最后一个元素，其实在所有k中也算是最小，因此按照最小堆来就行了

        def get_range(nums):
            heapq.heapify(nums)
            rv = []
            while len(nums):
                seq = heapq.heappop(nums)
                item = seq.pop(0)
                if len(rv):
                    rv.append(item)
                elif len(seq) == 0:
                    rv.append(item)
                else:
                    heapq.heappush(nums, seq)
            return rv
            
        reversed_nums = [list(reversed([-i for i in n])) for n in nums]
        rev_seq = get_range(reversed_nums)
        print("rev_seq", [-r for r in rev_seq])
        rev_seq = [-rev_seq[-1], -rev_seq[0]]
        seq = get_range(nums)
        print("seq", seq)
        seq = [seq[0], seq[-1]]

        rev_gap = rev_seq[1] - rev_seq[0]
        seq_gap = seq[1] - seq[0]
        if rev_gap == seq_gap:
            return rev_seq if rev_seq[0] < seq[0] else seq 
        return rev_seq if rev_gap < seq_gap else seq 


        print(rv)
        return [-rv[0], -rv[-1]]  # 选取开头结尾就行了。。。

import heapq

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # 看评论得到的思路，k路归并，看到这几个字就思路了。。。
        # 从第一个快被消灭的元素中获取最后一个元素，其实在所有k中也算是最小，因此按照最小堆来就行了
        nums = [list(reversed([-i for i in n])) for n in nums]
        heapq.heapify(nums)
        rv = []
        while len(nums):
            seq = heapq.heappop(nums)
            item = seq.pop(0)
            if len(rv):
                rv.append(item)
            elif len(seq) == 0:
                rv.append(item)
            else:
                heapq.heappush(nums, seq)
        print(rv)
        return [-rv[0], -rv[-1]]  # 选取开头结尾就行了。。。

import heapq

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # 看评论得到的思路，k路归并，看到这几个字就思路了。。。
        # 从第一个快被消灭的元素中获取最后一个元素，其实在所有k中也算是最小，因此按照最小堆来就行了
        if len(nums) == 1:  # 只有一个元素的话比较特别，不额外处理返回的就是最后一个元素，也即最大元素
            return [nums[0][0], nums[0][0]]
        heapq.heapify(nums)
        rv = []
        while len(nums):
            seq = heapq.heappop(nums)
            item = seq.pop(0)
            if len(rv):
                rv.append(item)
            elif len(seq) == 0:
                rv.append(item)
            else:
                heapq.heappush(nums, seq)
        return [rv[0], rv[-1]]  # 选取开头结尾就行了。。。