C ++中的K个空插槽
假设我们连续有N个灯泡，它们的编号从1到N。首先，所有灯泡都关闭了。我们可以每天只打开一个灯泡，直到N天后所有灯泡都打开。如果我们有一个长度为N的阵列灯泡，其中bulbs[i]=x，则表明在第（i+1）天，我们将在位置x处打开灯泡。如果我们有另一个整数K，则得出最小天数，以至于存在两个打开的灯泡，而它们之间恰好有K个灯泡全部熄灭。如果没有这样的日子，则返回-1。
因此，如果输入像灯泡：[1,3,2]且K=1，则输出将为2
在第一天：bulbs[0]=1，第一个灯泡打开：[1,0,0]
在第二天：bulbs[1]=3，然后打开第三个灯泡：[1,0,1]
在第三天：bulbs[2]=2，然后打开第二个灯泡：[1,1,1]
我们将返回2，因为在第二天，灯泡上有两个灯泡，而灯泡之间有一个灯泡。
为了解决这个问题，我们将遵循以下步骤-
n：=灯泡尺寸
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
天[bulbs[i]-1]=i+1
左：=0，右：=k+1，ret：=inf
对于初始化i：=0，当right<n时，更新（将i增加1），执行-
如果我是正确的，那么-
左：=我
右：=i+k+1
ret：=最小的ret，最大的天数[left]和days[right]
如果days[i]<days[left]或days[i]<=days[right]，则-
返回（如果ret与inf相同，则为-1，否则为ret）
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
vector<int> days(n);
for (int i = 0; i < n; i++) {
days[bulbs[i] - 1] = i + 1;
}
int left = 0;
int right = k + 1;
int ret = INT_MAX;
for (int i = 0; right < n; i++) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) {
ret = min(ret, max(days[left], days[right]));
}
left = i;
right = i + k + 1;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,2};
cout << (ob.kEmptySlots(v, 1));
}输入值
{1,3,2},输出结果
2