Giả sử chúng ta có N bóng đèn trong một hàng và được đánh số từ 1 đến N. Lúc đầu, tất cả bóng đèn đều tắt. Chúng ta có thể bật đúng một bóng đèn mỗi ngày cho đến khi tất cả bóng đèn bật sau N ngày. Nếu chúng ta có mảng bulbs độ dài N với bulbs[i] = x điều này chỉ ra rằng vào ngày (i+1)th, chúng ta sẽ bật bóng đèn tại vị trí x. Nếu chúng ta có một số nguyên K khác, sao cho ra ngày nhỏ nhất sao cho tồn tại hai bóng đèn đã bật có chính xác K bóng đèn giữa chúng đều tắt. Nếu không có ngày như vậy, trả về -1.
Vì vậy, nếu đầu vào là bulbs: [1,3,2] và K = 1, đầu ra sẽ là 2 vì
Ngày đầu tiên: bulbs[0] = 1, bóng đèn đầu tiên bật: [1,0,0]
Ngày thứ hai: bulbs[1] = 3, bóng đèn thứ ba bật: [1,0,1]
Ngày thứ ba: bulbs[2] = 2, bóng đèn thứ hai bật: [1,1,1]
Chúng ta trả về 2 vì vào ngày thứ hai, có hai bóng đèn bật với một bóng đèn tắt giữa chúng.
Để giải quyết, chúng ta sẽ làm theo các bước:
n := kích thước bulbs
Khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), làm:
days[bulbs[i] - 1] = i + 1
left := 0, right := k + 1, ret := inf
Khởi tạo i := 0, khi right < n, cập nhật (tăng i lên 1), làm:
nếu days[i] < days[left] hoặc days[i] <= days[right], thì:
nếu i giống right, thì:
ret := nhỏ nhất của ret và lớn nhất của days[left] và days[right]
left := i
right := i + k + 1
Trả về (nếu ret giống inf, thì -1, ngược lại ret)
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int kEmptySlots(vector<int>& bulbs, int k) { int n = bulbs.size(); vector<int> 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; } }; main(){ Solution ob; vector<int> v = {1,3,2}; cout << (ob.kEmptySlots(v, 1)); }Đầu vào
{1,3,2},Đầu ra
2