Задача о максимальном расстоянии до ближайшего занятого места часто формулируется так: есть ряд мест (например, скамейки или кресла), некоторые из них заняты (обозначены 1), остальные свободны (0). Нужно найти свободное место, которое максимально удалено от ближайшего занятого.

Техника решения:

Пройти по массиву и для каждого свободного места вычислить расстояние до ближайшего занятого.
Для этого удобно использовать два прохода:
- Слева направо: для каждого места запомнить расстояние до ближайшего занятого слева.
- Справа налево: аналогично для правой стороны.
Для каждого свободного места взять минимум из двух расстояний — это расстояние до ближайшего занятого.
Найти максимальное из этих минимальных расстояний.

Пример на Go:

func maxDistToClosest(seats []int) int {
    n := len(seats)
    leftDist := make([]int, n)
    rightDist := make([]int, n)

    // Инициализация
    for i := 0; i < n; i++ {
        leftDist[i] = n
        rightDist[i] = n
    }

    // Слева направо
    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            leftDist[i] = 0
        } else if i > 0 {
            leftDist[i] = leftDist[i-1] + 1
        }
    }

    // Справа налево
    for i := n - 1; i >= 0; i-- {
        if seats[i] == 1 {
            rightDist[i] = 0
        } else if i < n-1 {
            rightDist[i] = rightDist[i+1] + 1
        }
    }

    maxDist := 0
    for i := 0; i < n; i++ {
        if seats[i] == 0 {
            dist := leftDist[i]
            if rightDist[i] < dist {
                dist = rightDist[i]
            }
            if dist > maxDist {
                maxDist = dist
            }
        }
    }
    return maxDist
}

Такой подход эффективен и работает за O(n).

Объясните технику решения задачи о максимальном расстоянии до ближайшего занятого места