/* Kinodes asendid on paarsustatud ühel real. Uus vaataja valib koha, et istuda võimalikult kaugel teistest vaatajatest real. See tähendab, et kaugus kohast, kuhu ta istub, kuni lähima vaatajani, peaks olema maksimaalne. Garanteeritakse, et alati on vabad kohad ja et juba istub vähemalt üks vaataja. Kirjutage funktsioon, mis, lähtudes antud kohtade real (nullide ja ühekordsete massiiv), tagastab kauguse valitud kohast. Sisend: [1, 0, 0, 0, 0, 1] Väljund: 2 Sisend: [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] Väljund: 2 Sisend: [1, 0, 1, 0] Väljund: 1 */

Funktsioon peab leidma koha (nulliga tähistatud indeks), kus kaugus lähima hõivatud koha (üksed) juurest on maksimaalne.

Lahenduse idee:

• Läbi massiivi, iga vaba koha jaoks arvutada kaugus lähima hõivatud koha juurest.
• Tagastada see maksimaalne kaugus.

Optimaalne viis — üks läbimine, arvutades kaugused lähima ühesid vasakul ja paremal.

Näide Go keeles:

func maxDistance(seats []int) int {
    n := len(seats)
    leftDist := make([]int, n)
    rightDist := make([]int, n)

    // Täida kaugused lähima hõivatud koha juurest vasakul
    dist := n
    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        leftDist[i] = dist
    }

    // Täida kaugused lähima hõivatud koha juurest paremal
    dist = n
    for i := n - 1; i >= 0; i-- {
        if seats[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        rightDist[i] = dist
    }

    maxDist := 0
    for i := 0; i < n; i++ {
        if seats[i] == 0 {
            // Minimaalne kaugus lähima vaataja juurest
            d := leftDist[i]
            if rightDist[i] < d {
                d = rightDist[i]
            }
            if d > maxDist {
                maxDist = d
            }
        }
    }

    return maxDist
}

Seega tagastab funktsioon maksimaalse kauguse lähima vaataja juurest valitud kohas.