849. 到最近的人的最大距离

题目描述

给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。

至少有一个空座位，且至少有一人已经坐在座位上。

亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。

返回他到离他最近的人的最大距离。

示例 1：

输入：seats = [1,0,0,0,1,0,1]
输出：2
解释：如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。因此，他到离他最近的人的最大距离是 2 。

示例 2：

输入：seats = [1,0,0,0]
输出：3
解释：如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。这是可能的最大距离，所以答案是 3 。

示例 3：

输入：seats = [0,1]
输出：1

提示：

2 <= seats.length <= 2 * 10⁴
seats[i] 为 0 或 1
至少有一个 空座位
至少有一个 座位上有人

解法一：前缀数组 + 后缀数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


func max(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

func min(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num < res {
            res = num
        }
    }
    return res
}

func maxDistToClosest(seats []int) int {
    n := len(seats)
    leftPrev, rightPrev := math.MinInt32/2, math.MaxInt32/2
    leftArr, rightArr := make([]int, n), make([]int, n)
    ans := 0
    for i := 0; i < n; i++ {
        j := n - 1 - i
        if seats[i] == 1 {
            leftPrev = i
        } else {
            leftArr[i] = i - leftPrev
        }
        if seats[j] == 1 {
            rightPrev = j
        } else {
            rightArr[j] = rightPrev - j
        }
    }
    fmt.Println(leftArr, rightArr)
    for i := 0; i < n; i++ {
        ans = max(ans, min(leftArr[i], rightArr[i]))
    }
    return ans
}

解法二：一次遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func max(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

func maxDistToClosest(seats []int) int {
    n := len(seats)
    ans := 0
    prev := -1
    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            if prev == -1 {
                ans = i
            } else {
                ans = max(ans, (i+prev)/2-prev)
            }
            prev = i
        }
    }
    return max(ans, n-1-prev)
}