Skip to content

Latest commit

 

History

History
 
 

2009.Minimum-Number-of-Operations-to-Make-Array-Continuous

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2009.Minimum-Number-of-Operations-to-Make-Array-Continuous

我们只需要枚举这个连续区间的左端点即可。对于最优解而言,连续区间的左端点一定是落在nums的某一个数值上。假设存在某一个是最优解的连续区间,它的左端点不在nums里,那么我们可以将这个区间整体右移,直至左端点落在nums的某个数值上。这样,移动的过程中,区间的左边没有排除任何一个已经包含的nums的数值,而区间的右边还可能纳入新的nums的数值,肯定不会亏。

我们令nums的初始元素总个数是N。然后将nums去重、从小到大排序。

如果我们令这个连续区间的左端点在nums[i],那么我们会单调地增大j,往右探索区间的右端点nums[j]。假设我们希望构造的数值区间就是nums[i]到nums[j],那么其中已经包含的nums元素就有j-i+1个,剩余的“空隙”需要把数值区间外的nums挪过来填充。此时我们只需要简单地检查一下nums[j]-nums[i]+1的个数是否小于等于N即可。是的话,那么这个数值区间一定能填满,也有可能还有多余的元素,我们就将它们继续拼接在区间的右边即可。这样,对于固定的i,我们能找到最大的j,使得这个区间尽量地大,那么需要从外面拿进来填充的nums自然就会尽量的少了。

然后我们将i右移一位,发现与之匹配的最大的j肯定也是会往右边移动的。所以这就是一个双指针的问题。