Keshawn_lu's Blog

Leetcode 632. 最小区间

字数统计: 687阅读时长: 3 min
2020/08/01 Share

题目简介:

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

我们定义如果 b-a < d-c 或者在 b-a == d-ca < 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

思路:

这题与 76. 最小覆盖子串 的解题方法是差不多的,都是用哈希表+滑动窗口。

首先初始化哈希表,将元素的值及其所在的列表下标存入哈希表中。并在过程中保存所有元素的最大值和最小值作为边界值。

初始化right = left = Min,并且右边界开始右移扩大窗口,当map[right]存在时,将其对应的列表下标count[map[right][i]]++,当count[map[right][i]] == 1时,说明该列表刚有一个元素位于目前的区间中,sum++

sum == num.size()时,说明目前的区间已符合答案要求,尝试缩小区间并不断更新答案区间。

缩小区间时,左边界不断右移,直至sum != nums.size(),当map[left]存在时,将其对应的列表下标count[map[left][i]]--,当count[map[left][i]] == 0时,说明该列表没有元素位于目前的区间中,sum--

最后当right > Max时跳出循环,最后返回{res_left, res_right}即可。

tip:

  • 注意sum加减的时机。

代码如下:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {

unordered_map<int, vector<int>> map;

int Max = INT_MIN;
int Min = INT_MAX; //保存边界值

for(int i = 0; i < nums.size(); i++){

for(int j = 0; j < nums[i].size(); j++){

map[nums[i][j]].push_back(i);

Max = max(Max, nums[i][j]);
Min = min(Min, nums[i][j]);
}
}

int left = Min;
int right = Min;

int res_left = Min;
int res_right = Max;

int sum = 0;

vector<int> count(nums.size(), 0);

while(right <= Max){

if(map.count(right)){

for(int i = 0; i < map[right].size(); i++){

count[map[right][i]]++;

if(count[map[right][i]] == 1)
sum++; //该列表刚有数字进入区间
}
}

//开始缩小区间
while(sum == nums.size()){

if(right - left < res_right - res_left){

res_left = left;
res_right = right; //更新区间
}

if(map.count(left)){

for(int i = 0; i < map[left].size(); i++){

count[map[left][i]]--;

if(count[map[left][i]] == 0)
sum--; //该列表没有数字进入区间
}
}
left++;
}
right++;
}

return {res_left, res_right};

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: