849. Maximize Distance to Closest Person

LeetCode medium original: C# #array #csharp #leetcode #math #medium #two-pointers

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

Вам дан array, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).

Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.

Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

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

Exemplo:

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# solução

correspondente/original

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++ solução

rascunho automático, revisar antes de enviar

#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 solução

correspondente/original

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 solução

correspondente/original

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 solução

correspondente/original

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 solução

correspondente/original

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 считается бесконечностью, если справа нет занятого места.

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

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.