KC++の空のスロット

N個の電球が連続していて、1からNまでの番号が付けられているとします。最初は、すべての電球がオフになっています。 N日後にすべての電球がオンになるまで、毎日1つの電球をオンにすることができます。長さNのアレイ電球があり、bulbs [i] =xの場合、これは（i + 1）日目に位置xで電球をオンにすることを示します。別の整数Kがある場合、最小日数が2つ存在するように、それらの間に正確にK個の球根があり、すべてがオフになっています。そのような日がない場合は、-1を返します。

したがって、入力が球根のようなものである場合：[1,3,2]およびK =1の場合、出力は2 as

• 初日：bulbs [0] =1、最初の電球がオンになります：[1,0,0]

• 2日目：bulbs [1] =3、次に3番目の電球がオンになります：[1,0,1]

• 3日目：bulbs [2] =2、次に2番目の電球がオンになります：[1,1,1]

2日目には、2つの電球があり、1つの電球が間にあるため、2を返します。

これを解決するには、次の手順に従います-

• n：=電球のサイズ

• 初期化i：=0の場合、i

  • 日数[球根[i]-1]=i + 1

• 左：=0、右：=k + 1、ret：=inf

• 初期化i：=0の場合、右

  • days [i]

    • iが右と同じ場合、-

      • ret：=retの最小値と日数の最大値[左]と日数[右]

    • 左：=i

    • 右：=i + k + 1

• return（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