C++の電球スイッチャーIII

n個の電球がある部屋があるとします。これらの電球には、1からnまでの番号が付けられ、左から右に一列に並んでいます。最初は、すべての電球がオフになっています。瞬間k（0からn-1の範囲のkの場合）で、light[k]電球をオンにします。電球がオンになっていて、前のすべての電球（左側）もオンになっている場合にのみ、電球の色が青に変わります。オンになっているすべての電球が青色になっている瞬間の数を見つける必要があります。これが例です-

モーメントが1、2、4であるため、出力は3になります。

これを解決するには、次の手順に従います-

• ret：=0、セットxを定義、n：=リスト配列のサイズ、マップmを定義

• 最大ヒープベースの優先度キューpqを定義する

• 0からn–1の範囲のIの場合

  • m [light [i]]：=iそしてiをpqに挿入

• 1からnの範囲のIの場合

  • m[i]をx

    に挿入します

  • 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