Bộ Chuyển Đổi Đèn III Trong C++

Giả sử chúng ta có phòng với n bóng đèn, đánh số 1 đến n, xếp hàng từ trái sang right. Ban đầu tất cả tắt. Tại thời điểm k (k từ 0 đến n-1), bật đèn light[k]. Đèn chỉ chuyển sang màu xanh nếu nó bật và tất cả các đèn bên trái (trước nó) cũng đã bật. Tìm số lượng thời điểm mà tất cả các đèn đang bật đều là màu xanh.

Đầu ra là 3 (tại thời điểm 1, 2, 4).

Để giải quyết, chúng ta làm theo các bước:

ret := 0, tập hợp x, n := kích thước light, map m.
Định nghĩa max-heap priority queue pq.
Với i từ 0 đến n-1: m[light[i]] = i; pq.push(i).
Với i từ 1 đến n: x.insert(m[i]); khi pq không rỗng và pq.top() trong x: pq.pop(); ret += (pq rỗng hoặc pq.top() >= i) ? 1 : 0.
Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để 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;
    }
};

int main(){
    vector<int> v = {2,1,3,5,4};
    Solution ob;
    cout << (ob.numTimesAllBlue(v));
}

Đầu vào

[2,1,3,5,4]