Skip to content

Latest commit

 

History

History

632.Smallest-Range-Covering-Elements-from-K-Lists

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

632.Smallest-Range

本题的想法是:从小到大遍历所有的元素a,考虑如果以a为最小值,那么符合条件的最大值b是多少?

我们第一个考察的a必然是全局的最小值,假设它是nums[0]的第一个元素。那么我们如何找range的其他元素呢?显然为了使得range的范围最小、并且每个nums都被覆盖到,我们必然选取的都是每个nums[i]的第一个元素。我们把这个n个数放进一个有序容器里,自动排序后就知道最大值b是多少。因此b-a就可以确定下来了。

那么第二个考察的a就是全局的次小值。怎么找到这个次小值呢?我们只要把原来的a从有序容器里弹出去,再加进来nums[0]的第二个元素。此时有序容器里面的最小元素必然就是此时全局的次小值a。而且我们发现,现在容器里面的n个元素恰好覆盖了每个nums,并且都是各个nums里面的最小值(刨去已经弹走的不计)。所以我们用此时容器里面的最大值和最小值,就对应这当前range。

依次类推,我们每弹出一个当前容器里的最小值,为了保证每个nums都被覆盖到,必然就从那个数组里再补进一个最小值。此时容器里面的所有元素,就是当前全局最小值所对应的range(即恰好覆盖每个nums)。直至某次弹出最小值后,发现无法再从它的nums里补进新元素,说明再无法用剩下的元素取覆盖所有nums,即推出。

Leetcode Link