मान लीजिए कि हमारे पास n बल्ब वाला एक कमरा है, इन्हें 1 से n तक क्रमांकित किया गया है, बाएं से दाएं एक पंक्ति में व्यवस्थित किया गया है। प्रारंभ में, सभी बल्ब बंद कर दिए जाते हैं। पल में k (k के लिए 0 से n -1 की सीमा में), हम प्रकाश [k] बल्ब को चालू करते हैं। एक बल्ब का रंग नीले रंग में तभी बदलता है जब वह चालू हो और पिछले सभी बल्ब (बाईं ओर) भी चालू हों। हमें उन आघूर्णों की संख्या ज्ञात करनी है जिनमें सभी बल्बों को चालू किया गया नीला है। तो यह एक उदाहरण है -
आउटपुट 3 होगा क्योंकि क्षण 1, 2 और 4 हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ret :=0, एक सेट x परिभाषित करें, n :=सूची सरणी का आकार, एक नक्शा परिभाषित करें m
-
अधिकतम ढेर-आधारित प्राथमिकता कतार pq परिभाषित करें
-
I के लिए 0 से n - 1 की सीमा में
-
m[light[i]] :=i और i को pq में सम्मिलित करें
-
-
I के लिए 1 से n की सीमा में
-
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