План курса / Все задачи / Алгоритмы и структуры данных
Лучшее место на парковке
средне
# решено
Дан массив spots, где spots[i] = 1 — занятое место, spots[i] = 0 — свободное. Нужно выбрать свободное место так, чтобы расстояние до ближайшей занятой машины было максимальным. Вернуть это максимальное расстояние.
Расстояние между местами — разность их индексов. Для каждого свободного места рассматривается ближайшая занятая машина слева и справа; берётся минимум из двух расстояний. Если с одной стороны машин нет — учитывается только другая сторона.
Важно: гарантировано есть хотя бы одно свободное и хотя бы одно занятое место.
Пример 1:
Ввод: spots = [0,1,0,0,0,1,0,1,0]
Вывод: 2
Объяснение: лучшее место — индекс 3. Слева ближайшая машина на индексе 1 (расстояние 2), справа — на индексе 5 (расстояние 2). Минимум = 2. Для всех остальных свободных мест минимальное расстояние меньше.
Пример 2:
Ввод: spots = [0,0,0,1,0,1]
Вывод: 3
Объяснение: лучшее место — индекс 0. Машин слева нет, справа ближайшая на индексе 3 (расстояние 3).
Пример 3:
Ввод: spots = [1,0,0,1]
Вывод: 1
Ограничения:
len(spots) >= 2
Значение каждого элемента: 0 или 1
public class Solution
{
public static int BestParkingSpot(List<int> spots)
{
int l = 0;
int r = 0;
int result = 0;
while (l < spots.Count)
{
while (r + 1 < spots.Count && spots[r] == spots[r + 1])
{
r += 1;
}
// обновляем ответ, только если в плавающем окне были нули
if (spots[r] == 0)
{
if (l == 0 || r == spots.Count - 1)
{
// если 0 прижат к стенке слева или справа,
// то свободных мест будет r - l + 1, т. к. посадим в самый край
result = Math.Max(result, r - l + 1);
}
else
{
// окно располагается между 1-ами:
// поэтому находим число мест по формуле (r - l + 2) // 2
result = Math.Max(result, (r - l + 2) / 2);
}
}
l = r + 1;
r = r + 1;
}
return result;
}
}
#include <algorithm>
#include <vector>
using namespace std;
int bestParkingSpot(vector<int>& spots) {
int l = 0;
int r = 0;
int result = 0;
while (l < spots.size()) {
while (r + 1 < spots.size() && spots[r] == spots[r + 1]) {
r += 1;
}
// обновляем ответ, только если в плавающем окне были нули
if (spots[r] == 0) {
if (l == 0 || r == spots.size() - 1) {
// если 0 прижат к стенке слева или справа,
// то свободных мест будет r - l + 1, т. к. посадим в самый край
result = max(result, r - l + 1);
} else {
// окно располагается между 1-ами:
// поэтому находим число мест по формуле (r - l + 2) // 2
result = max(result, (r - l + 2) / 2);
}
}
l = r + 1;
r = r + 1;
}
return result;
}
package main
func max(a, b int) int {
if a > b {
return a
}
return b
}
func bestParkingSpot(spots []int) int {
l := 0
r := 0
result := 0
for l < len(spots) {
for r + 1 < len(spots) && spots[r] == spots[r + 1] {
r += 1
}
// обновляем ответ, только если в плавающем окне были нули
if spots[r] == 0 {
if l == 0 || r == len(spots) - 1 {
// если 0 прижат к стенке слева или справа,
// то свободных мест будет r - l + 1, т. к. посадим в самый край
result = max(result, r - l + 1)
} else {
// окно располагается между 1-ами:
// поэтому находим число мест по формуле (r - l + 2) // 2
result = max(result, (r - l + 2) / 2)
}
}
l = r + 1
r = r + 1
}
return result
}
import java.util.*;
public class Solution {
public int bestParkingSpot(List<Integer> spots) {
int l = 0;
int r = 0;
int result = 0;
while (l < spots.size()) {
while (r + 1 < spots.size() && spots.get(r) == spots.get(r + 1)) {
r += 1;
}
// обновляем ответ, только если в плавающем окне были нули
if (spots.get(r) == 0) {
if (l == 0 || r == spots.size() - 1) {
// если 0 прижат к стенке слева или справа,
// то свободных мест будет r - l + 1, т. к. посадим в самый край
result = Math.max(result, r - l + 1);
} else {
// окно располагается между 1-ами:
// поэтому находим число мест по формуле (r - l + 2) // 2
result = Math.max(result, (r - l + 2) / 2);
}
}
l = r + 1;
r = r + 1;
}
return result;
}
}
from typing import *
def best_parking_spot(spots: List[int]) -> int:
l = 0
r = 0
result = 0
while l < len(spots):
while r + 1 < len(spots) and spots[r] == spots[r + 1]:
r += 1
# обновляем ответ, только если в плавающем окне были нули
if spots[r] == 0:
# если 0 прижат к стенке слева или справа,
# то свободных мест будет r - l + 1, т. к. посадим в самый край
if l == 0 or r == len(spots) - 1:
result = max(result, r - l + 1)
# окно располагается между 1-ами:
# поэтому находим число мест по формуле (r - l + 2) // 2
else:
result = max(result, (r - l + 2) // 2)
l = r + 1
r = r + 1
return result
export function bestParkingSpot(spots) {
let l = 0;
let r = 0;
let result = 0;
while (l < spots.length) {
while (r + 1 < spots.length && spots[r] === spots[r + 1]) {
r += 1;
}
// обновляем ответ, только если в плавающем окне были нули
if (spots[r] === 0) {
if (l === 0 || r === spots.length - 1) {
// если 0 прижат к стенке слева или справа,
// то свободных мест будет r - l + 1, т. к. посадим в самый край
result = Math.max(result, r - l + 1);
} else {
// окно располагается между 1-ами:
// поэтому находим число мест по формуле (r - l + 2) // 2
result = Math.max(result, Math.floor((r - l + 2) / 2));
}
}
l = r + 1;
r = r + 1;
}
return result;
}
