Сложность: hard
У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.
Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.
Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.
Пример:
Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.
👨💻 Алгоритм:
1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.
2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.
3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.
😎 Решение:
class Solution {
function kEmptySlots($bulbs, $k) {
$active = [];
$day = 0;
foreach ($bulbs as $bulb) {
$day++;
$active[] = $bulb;
sort($active);
$index = array_search($bulb, $active);
if ($index > 0 && $bulb - $active[$index - 1] - 1 == $k) {
return $day;
}
if ($index < count($active) - 1 && $active[$index + 1] - $bulb - 1 == $k) {
return $day;
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний