Maximize Distance to Closest Person

Leetcode #849 | Medium | Математика | Жадный алгоритм

Идея

Решается за один проход, сохраняем индекс последнего человека, изначально -1. Когда встречаем первого - res = i (в начале ряда), при каждой следующей встрече выгодно сесть посередине res = max(res, (i-prev)/2), после прохода цикла делаем проверку на конец ряда res = max(res, N-1-prev) - если в конце свободны места

Big-O

• Время O(N)
• Память O(1)

Код

class Solution {
    public int maxDistToClosest(int[] seats) {
        int prev = -1, res = 0, n = seats.length;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (prev == -1) res = i;
                else res = Math.max(res, (i - prev) / 2);
                prev = i;
            }
        }
        return Math.max(res, n - 1 - prev);
    }
}