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
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private static class Node {
        int listNum;
        int idx;
        int val;

        Node(int _listNum, int _idx, int _val) {
            listNum = _listNum;
            idx = _idx;
            val = _val;
        }
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            minHeap.offer(new Node(i, 0, nums.get(i).get(0)));
            max = Math.max(max, nums.get(i).get(0));
        }
        int intervalLength = Integer.MAX_VALUE;
        int left = -1000000, right = 1000000;
        while (!minHeap.isEmpty()) {
            Node currMinNode = minHeap.peek();
            int currIntervalLength = max - currMinNode.val;
            if (currIntervalLength < intervalLength || (currIntervalLength == intervalLength &&
                    currMinNode.val < left)) {
                left = currMinNode.val;
                right = max;
                intervalLength = currIntervalLength;
            }
            minHeap.poll();
            if (currMinNode.idx + 1 == nums.get(currMinNode.listNum).size()) {
                break;
            }
            Node newNode = new Node(currMinNode.listNum, currMinNode.idx + 1,
                    nums.get(currMinNode.listNum).get(currMinNode.idx + 1));
            minHeap.offer(newNode);
            max = Math.max(max, newNode.val);
        }
        return new int[] { left, right };
    }
}

看到了K lists, 自然而然想到了用heap. 想到的思路是先把每个list的第0个元素统一放到heap中去. 然后看heap中的最大值和最小值是谁. 这两个值就是两个边界. 然后把heap中最小的pop出去. 为什么要让最小的出去? 因为我们想让heap中的数字尽可能靠近, 于是去移走那个最小的. 然后把被移走的数字对应的list的下一个数字放进来. 重复这个过程, 然后找到全局的最小interval. 如果遇到某个元素被pop出来后, 它所在的list后面没东西了, 那么此时就可以break了, 因为我们要的是能覆盖所有的lists. 需要注意的是我们到一种情况的时候, 如何知道此时heap的最大值呢? 因为最小值我们需要, 最大值也需要啊. 我们维护了一个max变量. 这个变量记录着heap的最大值. 当有新元素进来的时候, 我们根据新元素的大小来适时更新max, 这也是39行干的事情.

时间复杂度:O(Nlogk)装heap用了O(log1+log2+…logk)=O(klogk).然后我们要走遍至少一个list的所有元素,因此是走N次,那就是O(Nlogk)k是nums的length也就是list的个数,N是list的length.
空间复杂度:O(k)用了堆.

为什么这个方法奏效? 我们的brute force是把所有的可能都走一遍, 也就是给定的list中每个list挑一个数字共同组成一种情况, 然后看能覆盖这种情况的range是什么. 但是我们能用逻辑去除很多不可能的结果, 从而让我们的执行时间大大降低. 会到我们的逻辑, 我们首先把所有list的头都装进了heap中. 然后计算此时的最大最小组成的range. 此时我们pop走了最小的那个数字, 之前解释是说为了让大家凑近. 如何数学或者逻辑证明而不是感觉这样是对的? 比如我们看第二小的数字所在的list, 如果把它换成它之后的某个数字, 其余heap中的数字不变, 那么组成的range只可能大, 不可能小, 因为第二小数字所在list的后面的数字都比第二小数字大, 那么后面的数字只会往后扩范围, 不会让范围缩减. 同理可以适用于所有的第三小, 第四小…以及最大的元素. 因此这些组合我们都可以排除, 不必让程序一一验证. 因此此时唯一可能让range缩小的, 就是让heap中最小的数字pop出去, 然后来一个稍微大点儿数字, 这样range是有可能缩的.

综上, 我们可以用逻辑排除我们brute force中的绝大多数情况, 只让程序帮我们找到验证可能的情况中我们要的答案.