Giả sử chúng ta có một căn phòng có n bóng đèn, chúng được đánh số từ 1 đến n, sắp xếp thành một hàng từ trái sang phải. Ban đầu, tất cả các bóng đèn đều tắt. Tại thời điểm k (với k trong khoảng 0 đến n - 1), ta bật [k] bóng đèn. Bóng đèn chỉ đổi màu thành xanh lam nếu nó đang bật và tất cả các bóng đèn trước đó (bên trái) cũng được bật. Chúng ta phải tìm số thời điểm mà tất cả các bóng đèn được bật có màu xanh lam. Đây là một ví dụ -
Đầu ra sẽ là 3 vì các thời điểm là 1, 2 và 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=0, xác định một tập hợp x, n:=kích thước của mảng danh sách, xác định một bản đồ m
-
xác định pq hàng đợi ưu tiên dựa trên heap tối đa
-
cho tôi trong phạm vi từ 0 đến n - 1
-
m [light [i]]:=i và chèn i vào pq
-
-
cho tôi trong phạm vi từ 1 đến n
-
chèn m [i] vào x
-
trong khi pq không trống và phần tử trên cùng của pq nằm trong tập hợp x,
-
xóa khỏi pq
-
-
ret:=ret + 1 khi (pq trống hoặc trên cùng của pq> =i), nếu không thì 0
-
-
trả lại res
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#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));
} Đầu vào
[2,1,3,5,4]
Đầu ra
3