N 개의 전구가 연속적으로 있고 1에서 N까지 번호가 매겨져 있다고 가정합니다. 처음에는 모든 전구가 꺼져 있습니다. N일 후에 모든 전구가 켜질 때까지 매일 정확히 하나의 전구를 켤 수 있습니다. 만약 우리가 길이가 N이고 전구[i] =x인 어레이 전구가 있다면 이것은 (i+1)일에 위치 x에서 전구를 켤 것임을 나타냅니다. 우리가 다른 정수 K를 가지고 있다면, 그 사이에 정확히 K개의 전구가 있고 모두 꺼져 있는 두 개의 켜진 전구가 존재하도록 최소 일수를 빼냅니다. 해당 요일이 없으면 -1을 반환합니다.
따라서 입력이 전구와 같은 경우:[1,3,2] 및 K =1이면 출력은 다음과 같이 2가 됩니다.
-
첫째 날:전구[0] =1, 첫 번째 전구가 켜짐:[1,0,0]
-
두 번째 날:전구[1] =3이고 세 번째 전구가 켜집니다:[1,0,1]
-
세 번째 날:전구[2] =2이고 두 번째 전구가 켜집니다:[1,1,1]
두 번째 날에는 2개의 켜진 전구가 있었고 그 사이에 1개의 꺼진 전구가 있었기 때문에 2를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=전구 크기
-
initialize i :=0의 경우, i
-
일[전구[i] - 1] =i + 1
-
-
왼쪽 :=0, 오른쪽 :=k + 1, ret :=inf
-
initialize i :=0의 경우 right
-
일[i] <일[왼쪽] 또는 일[i] <=일[오른쪽]이면 -
-
i가 맞다면 -
-
ret :=ret의 최소값 및 최대 일수[왼쪽] 및 일수[오른쪽]
-
-
왼쪽 :=나는
-
오른쪽 :=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