849. Maximize Distance to Closest Person

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium #two-pointers

LeetCode Static

Вам дан массив, представляющий ряд сидений, где 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.

C# решение

сопоставлено/оригинал

public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int n = seats.Length;
        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 = Math.Max(ans, Math.Min(left, right));
            }
        }
        return ans;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int maxDistToClosest(int[] seats) {
        int N = seats.length;
        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 = Math.max(ans, Math.min(left, right));
            }
        }

        return ans;
    }
}

JavaScript решение

сопоставлено/оригинал

var maxDistToClosest = function(seats) {
    let n = seats.length;
    let prev = -1, future = 0;
    let ans = 0;

    for (let i = 0; i < n; ++i) {
        if (seats[i] === 1) {
            prev = i;
        } else {
            while (future < n && (seats[future] === 0 || future < i)) {
                future++;
            }
            let left = prev === -1 ? n : i - prev;
            let right = future === n ? n : future - i;
            ans = Math.max(ans, Math.min(left, right));
        }
    }

    return ans;
};

Python решение

сопоставлено/оригинал

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        prev = -1
        future = 0
        ans = 0

        for i in range(n):
            if seats[i] == 1:
                prev = i
            else:
                while future < n and (seats[future] == 0 or future < i):
                    future += 1
                left = n if prev == -1 else i - prev
                right = n if future == n else future - i
                ans = max(ans, min(left, right))
        
        return ans

Go решение

сопоставлено/оригинал

func maxDistToClosest(seats []int) int {
    n := len(seats)
    prev := -1
    future := 0
    ans := 0

    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            prev = i
        } else {
            for future < n && (seats[future] == 0 || future < i) {
                future++
            }
            left := n
            if prev != -1 {
                left = i - prev
            }
            right := n
            if future != n {
                right = future - i
            }
            ans = max(ans, min(left, right))
        }
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

Найдите и верните максимальное расстояние до ближайшего занятого места.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.