n개의 전구가 있는 방이 있다고 가정해 보겠습니다. 전구는 1에서 n까지 번호가 매겨져 있고 왼쪽에서 오른쪽으로 일렬로 배열되어 있습니다. 처음에는 모든 전구가 꺼집니다. 순간 k(범위 0에서 n - 1의 k에 대해)에서 전구[k] 전구를 켭니다. 전구가 켜져 있고 이전 전구(왼쪽)도 모두 켜져 있는 경우에만 전구의 색이 파란색으로 바뀝니다. 켜진 전구가 모두 파란색이 되는 순간의 수를 찾아야 합니다. 이것은 예입니다 -
모멘트가 1, 2, 4이므로 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=0, 세트 x 정의, n :=목록 배열의 크기, 맵 정의 m
-
최대 힙 기반 우선 순위 큐 pq 정의
-
0 ~ n – 1 범위의 I
-
m[light[i]] :=i 및 pq에 i 삽입
-
-
범위 1에서 n까지의 I에 대해
-
x에 m[i] 삽입
-
pq가 비어 있지 않고 pq의 최상위 요소가 집합 x에 있는 동안
-
pq에서 삭제
-
-
ret :=ret + 1(pq가 비어 있거나 pq>=i의 맨 위)일 때, 그렇지 않으면 0
-
-
반환 해상도
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ret = 0;
set <int> x;
int n = light.size();
map <int, int> m;
priority_queue <int, vector <int>, greater <int> > pq;
for(int i = 0; i < n; i++){
m[light[i]] = i;
pq.push(i);
}
for(int i = 1; i <=n; i++){
x.insert(m[i]);
while(!pq.empty() && x.count(pq.top()))pq.pop();
ret += (pq.empty() || (pq.top() >= i));
}
return ret;
}
};
main(){
vector<int> v = {2,1,3,5,4};
Solution ob;
cout << (ob.numTimesAllBlue(v));
} 입력
[2,1,3,5,4]
출력
3