Bulb Switcher III ใน C++ : นับ Moment ที่หลอดไฟเปิดทั้งหมดเป็นสีน้ำเงิน

มีหลอดไฟ n ดวง (1..n) เรียงซ้าย-ขวา เริ่มต้น **ปิดทั้งหมด** ที่ Moment k (0-indexed) เปิดหลอด light[k]

หลอดจะกลายเป็น **สีน้ำเงิน (Blue)** ก็ต่อเมื่อ **มันเปิดอยู่** และ **หลอดด้านซ้ายทั้งหมดเปิดอยู่แล้ว** (Prefix All On)

หาจำนวน **Moments** ที่ **หลอดที่เปิดอยู่ทั้งหมด เป็นสีน้ำเงินหมด** (All Turned On Bulbs Are Blue)

ตัวอย่าง

light = [2,1,3,5,4]

Moment 0: On 2 -> [Off, On, Off, Off, Off] -> Blue? No (1 is off)
Moment 1: On 1 -> [On, On, Off, Off, Off] -> Blue? Yes (1,2 on, all left of 2 on) -> Moment 1
Moment 2: On 3 -> [On, On, On, Off, Off] -> Blue? Yes (1,2,3 on) -> Moment 2
Moment 3: On 5 -> [On, On, On, Off, On] -> Blue? No (4 is off)
Moment 4: On 4 -> [On, On, On, On, On] -> Blue? Yes -> Moment 4
Total Blue Moments: 3 (Moments 1, 2, 4)

Output: 3

แนวทาง: Track Max Turned On Index

Key Insight: ทุกหลอดที่เปิดจะเป็นสีน้ำเงิน **ก็ต่อเมื่อ** หลอดที่เปิดอยู่มี Index **ต่อเนื่องจาก 1** (คือ Max Index ที่เปิด = จำนวนหลอดที่เปิด)

• เก็บ maxOn = 0 (Max Index ที่เปิดไปแล้ว)
• เก็บ countOn = 0 (จำนวนหลอดที่เปิดไปแล้ว)
• แต่ละ Moment: maxOn = max(maxOn, light[i]), countOn++
• ถ้า maxOn == countOn -> **All On Bulbs Are Blue** -> ans++

ตัวอย่างโค้ด C++ (Optimized O(N))

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int maxOn = 0, countOn = 0, ans = 0;
        for (int x : light) {
            maxOn = max(maxOn, x);
            countOn++;
            if (maxOn == countOn) ans++; // Prefix 1..maxOn all on
        }
        return ans;
    }
};

Input / Output

Input:  [2,1,3,5,4]
Output: 3

ความซับซ้อน (Complexity)

• Time: O(N) — Single Pass
• Space: O(1)

หมายเหตุ

โค้ดต้นฉบับใช้ Priority Queue + Set ซับซ้อนเกินจริง วิธี maxOn == countOn นี้ **Optimal และเข้าใจง่ายที่สุด** ครับ