Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

最小区间

Posted on In , ,
Symbols count in article: 2.9k Reading time ≈ 3 mins.

来自Leetcode632题最小区间

你有 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个大根堆以及一个小根堆，注意到这k个数组是升序排列的有序数组，因而初始化时将这k个数组的首元素放进堆里；之后遍历小根堆，退出条件是小根堆的大小小于k，当小根堆的大小小于k时就不满足k个列表中的每个列表至少有一个数包含在其中。在遍历小根堆时，取出大根堆以及小根堆的元素，这样就满足了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
public int[] smallestRange(List<List<Integer>> nums) {
    //小根堆，记录元素的二维坐标
    Queue<int []> minQueue = new PriorityQueue<>(Comparator.comparingInt
            (arr -> nums.get(arr[0]).get(arr[1])));
    //大根堆，记录元素的二维坐标
    Queue<int []> maxQueue = new PriorityQueue<>((arr1,arr2) ->
            nums.get(arr2[0]).get(arr2[1]) - nums.get(arr1[0]).get(arr1[1]));
    int[] ans = {Integer.MIN_VALUE,Integer.MAX_VALUE};
    for(int i = 0 ; i < nums.size() ; ++i){
        //将每列的第一个元素都加进去
        int[] temp = new int[]{i,0};
        minQueue.offer(temp);
        maxQueue.offer(temp);
    }
    while (minQueue.size() == nums.size()){
        //取出小根堆堆顶元素
        int[] minArr = minQueue.poll();
        //取出大根堆堆顶元素
        int[] maxArr = maxQueue.peek();
        //此时在这两个元素至少包含所有数组的一个元素
        if((long)nums.get(maxArr[0]).get(maxArr[1]) - (long)nums.get(minArr[0]).get(minArr[1])
        < (long)ans[1] - ans[0]){
            ans[0] = nums.get(minArr[0]).get(minArr[1]);
            ans[1] = nums.get(maxArr[0]).get(maxArr[1]);
        }
        //比较过后可以丢弃掉小根堆的元素，同时添加下一元素到堆里
        if(minArr[1] < nums.get(minArr[0]).size() - 1){
            int[] newArr = {minArr[0],minArr[1] + 1};
            minQueue.offer(newArr);
            maxQueue.remove(minArr);
            maxQueue.offer(newArr);
        }
    }
    return ans;
}

不过堆的实现还是可以看看官方题解，只用维护一下小根堆，以及一个全局最大值，对应的next数组。

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
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int rangeLeft = 0, rangeRight = Integer.MAX_VALUE;
        int minRange = rangeRight - rangeLeft;
        int max = Integer.MIN_VALUE;
        int size = nums.size();
        int[] next = new int[size];
        //小根堆里维护的是k个列表的指针
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer index1, Integer index2) {
                return nums.get(index1).get(next[index1]) - nums.get(index2).get(next[index2]);
            }
        });
        for (int i = 0; i < size; i++) {
            priorityQueue.offer(i);
            max = Math.max(max, nums.get(i).get(0));
        }
        while (true) {
            int minIndex = priorityQueue.poll();
            int curRange = max - nums.get(minIndex).get(next[minIndex]);
            if (curRange < minRange) {
                minRange = curRange;
                rangeLeft = nums.get(minIndex).get(next[minIndex]);
                rangeRight = max;
            }
            next[minIndex]++;
            //这里的break也是和上面是一样的意思，为了维护k个列表的堆
            if (next[minIndex] == nums.get(minIndex).size()) {
                break;
            }
            //这里设置comparator，比较的其实是next[minIndex]里对应的数值
            priorityQueue.offer(minIndex);
            max = Math.max(max, nums.get(minIndex).get(next[minIndex]));
        }
        return new int[]{rangeLeft, rangeRight};
    }
}