849_maximize_distance_to_closest_person

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 * 104
• seats[i] 为 0 或 1
• 至少有一个 空座位
• 至少有一个 座位上有人

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(maxDistToClosest([]int{1, 0, 0, 0, 1, 0, 1}))                               // 2
    fmt.Println(maxDistToClosest([]int{1, 0, 0, 0}))                                        // 3
    fmt.Println(maxDistToClosest([]int{0, 1}))                                              // 1
    fmt.Println(maxDistToClosest([]int{0, 1, 1, 1, 0, 0, 1, 0, 0}))                         // 2
    fmt.Println(maxDistToClosest([]int{0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0})) // 3
}

// 找到最长的 0 序列，按序列边界是否为 1 来决定取中点还是边界
// 双指针
// 辣鸡解法
func maxDistToClosest(seats []int) int {
    n := len(seats)
    if n <= 0 {
        return n
    }

    // 0 开头或 0 结尾的两种特殊 case
    maxStart, maxEnd := 0, 0
    if seats[0] == 0 {
        for i := 0; i < n && seats[i] == 0; i++ {
            maxStart++
        }
    }
    if seats[n-1] == 0 {
        for i := n - 1; i >= 0 && seats[i] == 0; i-- {
            maxEnd ++
        }
    }

    // 快慢指针找出位于中间的最长 0 序列
    slow := 0
    zeroEdges := make([]int, 2)
    for slow < n {
        fast := slow
        for fast < n && seats[fast] == 0 {
            fast++
        }
        if fast-1 > slow {
            if fast-1-slow > zeroEdges[1]-zeroEdges[0] {
                zeroEdges[0], zeroEdges[1] = slow, fast-1
            }
        }
        slow++
    }

    return max(maxStart, maxEnd, (zeroEdges[1]-zeroEdges[0])/2+1)
}

func max(x, y, z int) int {
    if x > y {
        if x > z {
            return x
        }
        return z
    } else {
        if y > z {
            return y
        }
        return z
    }
}