本文主要是介绍最小区间00，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
最小区间00
题目描述
注意点
- -10^5 <= nums[i][j] <= 10^5
- nums[i] 按非递减顺序排列
- 找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中
解答思路
- 参照题解，根据滑动窗口完成本题
- 首先将所有的元素都提取出来并按升序进行排序放进arr中，arr中每个元素有两个信息，arr[i][0]表示元素的值，arr[i][1]表示元素在nums中对应哪个列表中
- 排序后不断在arr中移动滑动窗口，保证窗口中有每个列表中的元素，找到满足该条件下窗口对应的最小区间
代码
class Solution {public int[] smallestRange(List<List<Integer>> nums) {int[] res = {-1000001, 1000001};int n = 0;for (List<Integer> list : nums) {n += list.size();}// 升序排序nums中所有的元素，arr[i][0]表示元素的值，arr[i][1]表示元素在nums中第几个列表int[][] arr = new int[n][2];int idx = 0;for (int i = 0; i < nums.size(); i++) {for (int num : nums.get(i)) {arr[idx][0] = num;arr[idx][1] = i;idx++;}}Arrays.sort(arr, (x, y) -> (x[0] - y[0]));// 滑动窗口中包含了哪些列表的元素int[] windowTab = new int[nums.size()];// 滑动窗口中包含了几个列表的元素int windowSum = 0;int left = 0, right = 0;while (right < arr.length) {if (windowTab[arr[right][1]] == 0) {windowSum++;}windowTab[arr[right][1]]++;// 滑动窗口中包含了所有列表的元素if (windowSum == windowTab.length) {// 尽量缩小滑动窗口while (windowTab[arr[left][1]] > 1) {windowTab[arr[left][1]]--;left++;}if (arr[right][0] - arr[left][0] < res[1] - res[0]) {res[0] = arr[left][0];res[1] = arr[right][0];}}right++;}return res;}public List<int[]> fillAllIncreaseNum(List<List<Integer>> nums) {int[] idxArr = new int[nums.size()];List<int[]> list = new ArrayList<>();while (true) {boolean hasNum = false;int minVal = Integer.MAX_VALUE;int minLoc = -1;for (int i = 0; i < idxArr.length; i++) {if (idxArr[i] >= nums.get(i).size()) {continue;}hasNum = true;if (nums.get(i).get(idxArr[i]) < minVal) {minVal = nums.get(i).get(idxArr[i]);minLoc = i;}}if (!hasNum) {break;}int[] arr = {minVal, minLoc};list.add(arr);idxArr[minLoc]++;}return list;}
}
关键点
- 滑动窗口的思想
- 注意在移动滑动窗口寻找包含每个列表的元素时，窗口应尽可能小，越小的窗口其区间一定更小
这篇关于最小区间00的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
