ধরুন আমাদের n বাল্ব সহ একটি ঘর আছে, এগুলি 1 থেকে n পর্যন্ত সংখ্যাযুক্ত, বাম থেকে ডানে একটি সারিতে সাজানো। প্রাথমিকভাবে, সমস্ত বাল্ব বন্ধ করা হয়। মুহুর্তে k (k এর জন্য 0 থেকে n - 1 পরিসরে), আমরা আলো [k] বাল্বটি চালু করি। একটি বাল্ব শুধুমাত্র তখনই নীল রঙে পরিবর্তন করে যখন এটি চালু থাকে এবং পূর্ববর্তী সমস্ত বাল্বগুলিও (বাম দিকে) চালু থাকে। আমাদের এমন মুহুর্তগুলির সংখ্যা খুঁজে বের করতে হবে যেখানে সমস্ত বাল্ব চালু হয়েছে নীল। তাই এটি একটি উদাহরণ -
আউটপুট 3 হবে কারণ মুহূর্তগুলি 1, 2 এবং 4।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0, একটি সেট সংজ্ঞায়িত করুন x, n :=তালিকা অ্যারের আকার, একটি মানচিত্র সংজ্ঞায়িত করুন m
-
একটি সর্বোচ্চ হিপ-ভিত্তিক অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন -
আমি 0 থেকে n – 1
পরিসরে-
m[আলো[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
