roma-dxunvrs
22 lines
1.1 KiB
Markdown
22 lines
1.1 KiB
Markdown
Leetcode #849 | #Medium | [[Математика]] | [[Жадный алгоритм]]
|
|
## Идея
|
|
Решается за один проход, сохраняем индекс последнего человека, изначально -1. Когда встречаем первого - res = i (в начале ряда), при каждой следующей встрече выгодно сесть посередине res = max(res, (i-prev)/2), после прохода цикла делаем проверку на конец ряда res = max(res, N-1-prev) - если в конце свободны места
|
|
## [[Big-O]]
|
|
- Время ```O(N)```
|
|
- Память ```O(1)```
|
|
## Код
|
|
```Java
|
|
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);
|
|
}
|
|
}
|
|
``` |