题目描述

在一排座位（seats）中，1 代表有人坐在座位上，0 代表座位上是空的。

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

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

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

样例

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

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

注意

• 1 <= seats.length <= 20000
• seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。

算法

(暴力枚举) $O(n)$

1. 用一个变量记录上一个 1 的位置，每次遇到 1 时，更新答案和 last。特殊处理第一个 1。
2. 最后还需要试一下放到最后的位置上和 last 的距离，更新答案。

时间复杂度

• 仅遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 定义了常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int n = seats.size();
        int last = -1, ans = -1;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (ans == -1)
                    ans = i;
                else
                    ans = max(ans, (i - last) / 2);
                last = i;
            }
        }
        ans = max(ans, n - 1 - last);
        return ans;
    }
};