LeetCode632-最小区间

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/smallest-range/

中文链接：https://leetcode-cn.com/problems/smallest-range/

题目详述

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

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

示例 1:

1
2
3
4
5
6
输入:[[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. -105 <= 元素的值 <= 105
  4. 对于使用Java的用户，请注意传入类型已修改为List<List< Integer>>。重置代码模板后可以看到这项改动。

题目详解

运用双指针的思想，具体到本题就是 k 指针。

  • k 个指针分别指向 k 个排序数组，这 k 个指针所指元素构成了一个区间。
  • 这 k 个元素内的最小值和最大值可能构成一个满足条件的最小区间。
  • 每次剔除掉 k 个元素中的最小值，并将对应指针往后移一位，加入下一个元素（当指针超过数组下标时整个迭代过程就停止了）。
  • 在迭代的规程中维护最小区间，迭代结束就得到了最终的结果。
  • 现在问题的关键变成了如何每次取得这 k 个元素的最大值和最小值。
  • 用一个小顶堆是比较合适的，用它来获取最小值，而最大值可以通过每次加入元素到小顶堆时维护一个变量来得到。
  • 时间复杂度为 O(nlogk)。

实现的过程类似于 LeetCode23-合并K个排序链表。

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
44
45
public class LeetCode_00632 {

    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        PriorityQueue<Data> queue = new PriorityQueue<>(k);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < k; ++i) {
            int val = nums.get(i).get(0);
            queue.offer(new Data(val, i));
            max = Math.max(max, val);
        }
        int[] res = new int[] {queue.peek().val, max};
        int[] index = new int[k];
        while (true) {
            Data data = queue.poll();
            if (max - data.val < res[1] - res[0]) {
                res[0] = data.val;
                res[1] = max;
            }
            int i = data.i;
            if (++index[i] == nums.get(i).size()) {
                break;
            }
            int val = nums.get(i).get(index[i]);
            queue.offer(new Data(val, i));
            max = Math.max(max, val);
        }
        return res;
    }

    class Data implements Comparable<Data> {
        int val;
        int i;

        public Data(int val, int i) {
            this.val = val;
            this.i = i;
        }

        @Override
        public int compareTo(Data o) {
            return Integer.compare(val, o.val);
        }
    }
}

也可以不创建额外的一个类，直接用优先队列存储下标，不过排序规则同样需要我们自定义，获取元素的值时要复杂一点。

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
public class LeetCode_00632 {

    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        int[] index = new int[k];
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(nums.get(o1).get(index[o1]), nums.get(o2).get(index[o2]));
            }
        });
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < k; ++i) {
            queue.offer(i);
            max = Math.max(max, nums.get(i).get(0));
        }
        int[] res = new int[] {nums.get(queue.peek()).get(0), max};
        while (true) {
            int i = queue.poll();
            List<Integer> list = nums.get(i);
            if (max - list.get(index[i]) < res[1] - res[0]) {
                res[0] = list.get(index[i]);
                res[1] = max;
            }
            if (++index[i] == list.size()) {
                break;
            }
            queue.offer(i);
            max = Math.max(max, list.get(index[i]));
        }
        return res;
    }
}