สมมติว่าเรามีห้องที่มีหลอดไฟ n ดวง ซึ่งจะมีหมายเลขตั้งแต่ 1 ถึง n เรียงกันเป็นแถวจากซ้ายไปขวา ในขั้นต้น หลอดไฟทั้งหมดจะถูกปิด ในขณะนี้ k (สำหรับ k ในช่วง 0 ถึง n - 1) เราเปิดหลอดไฟ[k] หลอดไฟเปลี่ยนสีเป็นสีน้ำเงินก็ต่อเมื่อเปิดอยู่และหลอดไฟก่อนหน้าทั้งหมด (ทางด้านซ้าย) ก็เปิดอยู่ด้วย เราต้องหาจำนวนช่วงเวลาที่หลอดไฟเปิดทั้งหมดเป็นสีน้ำเงิน นี่คือตัวอย่าง −
ผลลัพธ์จะเป็น 3 เนื่องจากช่วงเวลาคือ 1, 2 และ 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0 กำหนดชุด x, n :=ขนาดของรายการอาร์เรย์ กำหนดแผนที่ m
-
กำหนด pq ลำดับความสำคัญสูงสุดตามฮีป
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
m[light[i]] :=i และแทรก i ลงใน pq
-
-
สำหรับฉันอยู่ในช่วง 1 ถึง n
-
แทรก 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
