“愿你逐梦成真，不负年少所想”

你好，八月~

2020.8

8.1

632.最小区间

官方题解✒

  • 问题转化：给定 k个列表，需要找到最小区间，使得每个列表都至少有一个数在该区间中。该问题可以转化为，从 k个列表中各取一个数，使得这 k个数中的最大值与最小值的差最小。
  • 由于 k个列表都是升序排列的，因此对每个列表维护一个指针，通过指针得到列表中的元素，指针右移之后指向的元素一定大于或等于之前的元素。
  • 使用最小堆维护 k个指针指向的元素中的最小值，同时维护堆中元素的最大值。初始时，k个指针都指向下标 0，最大元素即为所有列表的下标 0位置的元素中的最大值。每次从堆中取出最小值，根据最大值和最小值计算当前区间，如果当前区间小于最小区间则用当前区间更新最小区间，然后将对应列表的指针右移，将新元素加入堆中，并更新堆中元素的最大值。
  • 如果一个列表的指针超出该列表的下标范围，则说明该列表中的所有元素都被遍历过，堆中不会再有该列表中的元素，因此退出循环。
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
class Solution {
	public int[] smallestRange(List<List<Integer>> nums) {
		int rangeLeft = 0;
		int rangeRight = Integer.MAX_VALUE;
		int minRange = rangeRight - rangeLeft;
		int max = Integer.MIN_VALUE;
		int size = nums.size();
		int[] next = new int[size];
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return nums.get(o1).get(next[o1]) - nums.get(o2).get(next[o2]);
			}
		});
		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]++;
			if (next[minIndex] == nums.get(minIndex).size()) {
				break;
			}
			priorityQueue.offer(minIndex);
			max = Math.max(max, nums.get(minIndex).get(next[minIndex]));
		}
		return new int[]{rangeLeft, rangeRight};
	}
}