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