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

好题

力扣原题链接（点我直达）

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

第一版，有参考别人

保存首位连续0的个数，和（中间连续0的个数+1）/2，最近进行比较即可

执行用时 :16 ms, 在所有 cpp 提交中击败了74.71%的用户

内存消耗 :10 MB, 在所有 cpp 提交中击败了82.11%的用户

int maxDistToClosest(vector<int>& seats) {

    int lowZeroCut=0, highZeroCut = 0,i = 0, len = seats.size();
    int j = len - 1;

    while (seats[i] == 0 && i < len) {
        lowZeroCut++;
        i++;
    }
    i++;//i已经等于1了，跳过即可

    while (seats[j] == 0 && j >=0) {
        highZeroCut++;
        j--;
    }
    //注意这里不可以再像上面一样再跳过j了，还需要他在下面进行一个判断条件
//中间连续的0的判断依据就是遇到1了即可以判断了，仔细想想
    highZeroCut = max(lowZeroCut, highZeroCut);//保存此时的最大值
    lowZeroCut = 0;
    int cut = 0;
    while (i <= j) {
        if (seats[i++] == 0)
        {
            cut++;
        }
        else {//遇到1了
            lowZeroCut = max(cut, lowZeroCut);
            cut = 0;
        }
    }

    highZeroCut = max(highZeroCut, (lowZeroCut + 1) / 2);
    return highZeroCut;

}