【Leetcode 每日一题】632. 最小区间

问题背景

你有 $k$ 个 非递减排列 的整数列表。找到一个 最小 区间，使得 $k$ 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 $b-a<d-c$ 或者在 $b-a==d-c$ 时 $a<c$，则区间 $[a,b]$ 比 $[c,d]$ 小。
数据约束

• $nums.length=k$
• $1\le k\le 3500$
• $1\le nums[i].length\le 50$
• $-10^5\le nums[i][j]\le 10^5$
• $nums[i]$ 按非递减顺序排列

解题过程

解决这个问题的关键在于，想明白答案是从每个区间的左端获得的。由于给定的列表中的子列表元素有序，所以对于某一个状态的问题列表而言，结果的左端点就是所有列表中第一个元素的最小值，结果的右端点就是所有列表中第一个元素的最大值。
不过由于题中区间的大小是由区间长度来决定的，所以有可能出现除了第一个元素以外的其他元素组成更小的区间的情况。因此还需要考虑使用第一个元素以外的元素时，能否构成更小的区间。也就是说，每一轮循环中，要做的是根据当前所有列表中最小元素确定右端点。因此，我们需要一个能够根据其中元素的情况来维护最小值的数据结构，选用最小堆。
堆中的元素可以是一个三元组，除了最小的元素，额外保存它所在的列表序号，以及在列表中的下标，这样可以方便地在题中所给列表 $nums$ 中进行定位。更新状态时，不必移除元素，改变堆顶三元组中的左端点即可。
这样做的时间复杂度是 $O(Llogk)$，其中 $L$ 是所有列表的长度之和，其中 $k$ 是题中所给数组 $nums$ 的长度。循环 $L$ 次，每次循环需要 $logk$ 量级的时间操作堆。空间复杂度是 $O(k)$，堆需要一定的空间来保存元素。

另一种思路是，记录每个元素所在的列表编号之后，将所有列表中的数字放在一起排序。
这时候问题就转变为，在有序序列中找到最短的子数组，使得其中包含每个列表中至少一个元素。子数组中包含的每个列表中的元素数量随着子数组长度增长而增加，可以滑窗。
这种思路的时间复杂度是 $O(LlogL)$ 或者 $O(L)$，其中 $L$ 是所有 $nums[i]$ 的长度之和。考虑到瓶颈在排序上，将默认排序算法 $TimSort$ 替换成昨天刚刚整理过的计数排序 $CountingSort$，可以有效提升性能。空间复杂度是 $O(L)$，需要额外空间来保存包含所有元素的数组。

具体实现

维护最小堆

class Solution {public int[] smallestRange(List<List<Integer>> nums) {// Java 中可以定义优先队列，自定义排序方式来作为堆PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((i1, i2) -> i1[0] - i2[0]);int right = Integer.MIN_VALUE;for(int i = 0; i < nums.size(); i++) {// 原列表中所有的第一个元素入堆int cur = nums.get(i).get(0);// 同时记录该元素在原列表中的坐标priorityQueue.offer(new int[]{cur, i, 0});// 右端点是所有第一个元素中的最大值right = Math.max(right, cur);}int resL = priorityQueue.peek()[0];int resR = right;// 堆顶三元组中下标为 2 的元素记录的是当前元素的位置，先自增表示下一个元素的位置// 循环结束的条件是出现某个列表里没有下一个元素，无法构成合法区间while(++priorityQueue.peek()[2] < nums.get(priorityQueue.peek()[1]).size()) {// 获取并更新堆顶三元组int[] top = priorityQueue.poll();top[0] = nums.get(top[1]).get(top[2]); // 经过自增，这里取得的是下一个元素// 取出来之后更新右端点right = Math.max(right, top[0]);// 复用三元组，将修改了值之后的新三元组入堆priorityQueue.offer(top);// 从调整之后的合法堆中获取当前第一个元素的最小值int left = priorityQueue.peek()[0];if(right - left < resR - resL) {resL = left;resR = right;}}return new int[] {resL, resR};}
}

排序后滑窗

class Solution {public int[] smallestRange(List<List<Integer>> nums) {// 计算保存所有元素需要的数组长度int length = 0;for(List<Integer> list : nums) {length += list.size();}// 将列表中所有元素记录到新数组中int[][] pairs = new int[length][2];int index = 0;for(int i = 0; i < nums.size(); i++) {for(int num : nums.get(i)) {pairs[index][0] = num;pairs[index++][1] = i;}}// 使用 Java 默认的 排序算法 TimSort// Arrays.sort(pairs, (a, b) -> a[0] - b[0]);// 自己实现二维计数排序 CountingSort2dcountingSort2d(pairs);int resL = pairs[0][0];int resR = pairs[length - 1][0];int diff = nums.size(); // diff 表示没有元素被包含的列表数量int[] count = new int[diff]; // 统计每个列表中被包含的元素数量int leftIndex = 0; // 记录当前左端点的所在的列表编号for(int[] pair : pairs) {int right = pair[0];int curIndex = pair[1];// 当前列表有元素被包含，diff 减少if(count[curIndex]++ == 0) {diff--;}while(diff == 0) {int left = pairs[leftIndex][0]; // 取出当前左端点// 满足条件的情况下更新答案if(right - left < resR - resL) {resL = left;resR = right;}// 更新左端点所在的列表编号curIndex = pairs[leftIndex][1];// 如果当前列表中没有元素被包含，diff 增加if(--count[curIndex] == 0) {diff++;}leftIndex++; // 移动左端点}}return new int[] {resL, resR};}private void countingSort2d(int[][] pairs) {// 查找数组中的最小最大值，确定映射范围int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;for(int[] pair : pairs) {min = Math.min(min, pair[0]);max = Math.max(max, pair[0]);}int range = max - min + 1;int[] count = new int[range];// 统计每个元素出现的次数for(int[] pair : pairs) {count[pair[0] - min]++;}// 改造成前缀分区的形式，方便快速地确定还原后的元素位置for(int i = 1; i < count.length; i++) {count[i] += count[i - 1];}int length = pairs.length;// 还原数组元素int[][] res = new int[length][2];for(int i = length - 1; i >= 0; i--) {int cur = pairs[i][0];res[--count[cur - min]] = pairs[i];}// 把结果回写到原数组中System.arraycopy(res, 0, pairs, 0, length);}
}