Сложность: medium
Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.
Верните это максимальное расстояние до ближайшего человека.
Пример:
Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation:
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.
👨💻 Алгоритм:
1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.
2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.
3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.
😎 Решение:
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int N = seats.size();
int prev = -1, future = 0;
int ans = 0;
for (int i = 0; i < N; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < N && (seats[future] == 0 || future < i)) {
future++;
}
int left = prev == -1 ? N : i - prev;
int right = future == N ? N : future - i;
ans = max(ans, min(left, right));
}
}
return ans;
}
};Ставь 👍 и забирай 📚 Базу знаний