K Empty Slots (ช่องว่าง K ช่อง) ใน C++

สมมติว่าเรามีหลอดไฟ N ดวงเรียงเป็นแถว และหมายเลข 1 ถึง N เริ่มต้นหลอดไฟทั้งหมดปิด เราสามารถเปิดหลอดไฟได้ทีละดวงทุกวัน จนหลอดไฟทั้งหมดเปิดหลังจาก N วัน หากเรามีอาเรย์ bulbs ขนาด N โดยที่ bulbs[i] = x หมายความว่า ในวันที่ (i+1) เราจะเปิดหลอดไฟที่ตำแหน่ง x หากเรามีจำนวนเต็มอีกตัว K โดยที่ เราต้องหา หมายเลขวันที่น้อยที่สุด ที่มีหลอดไฟเปิดอยู่สองดวง ที่มีหลอดไฟปิดอยู่ระหว่างกันพอดี K ดวง หากไม่มีวันแบบนั้น ให้คืนค่า -1

ดังนั้น หากอินพุทคือ bulbs: [1,3,2] และ K = 1 ผลลัพธ์จะเป็น 2 เนื่องจาก:

• วันที่ 1: bulbs[0] = 1, หลอดแรกเปิด: [1,0,0]

• วันที่ 2: bulbs[1] = 3, หลอดที่สามเปิด: [1,0,1]

• วันที่ 3: bulbs[2] = 2, หลอดที่สองเปิด: [1,1,1]

เราจะคืนค่า 2 เพราะในวันที่ 2 มีหลอดเปิดสองดวงที่มีหลอดปิดหนึ่งดวงอยู่ระหว่าง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n := ขนาดของ bulbs

• for i := 0 ถึง n-1: days[bulbs[i] - 1] = i + 1

• left := 0, right := k + 1, ret := INF

• for i := 0; right < n; i++:

  • ถ้า days[i] < days[left] หรือ days[i] <= days[right]:

    • ถ้า i == right: ret := min(ret, max(days[left], days[right]))

    • left := i, right := i + k + 1

• คืนค่า (ret == INF) ? -1 : ret

ตัวอย่างโค้ด

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

class Solution {
public:
    int kEmptySlots(vector& bulbs, int k) {
        int n = bulbs.size();
        vector days(n);
        for (int i = 0; i < n; i++) {
            days[bulbs[i] - 1] = i + 1;
        }
        int left = 0;
        int right = k + 1;
        int ret = INT_MAX;
        for (int i = 0; right < n; i++) {
            if (days[i] < days[left] || days[i] <= days[right]) {
                if (i == right) {
                    ret = min(ret, max(days[left], days[right]));
                }
                left = i;
                right = i + k + 1;
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    vector v = {1, 3, 2};
    cout << (ob.kEmptySlots(v, 1));
    return 0;
}

อินพุต

{1,3,2}, 1

เอาต์พุต

2