leetcode-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

解题

方法一：一次遍历

总共有三种情况

• 1.计算左边第一个有人的位置到左边的第一个位置距离（亚历克斯可以坐到最左边）
• 2.计算最右边有人的位置到最后一个位置距离（亚历克斯可以坐到最右边）
• 3.计算两个有人位置间的距离（亚历克斯可以坐到两个人中间）

取这三种情况的最大值就行了。

class Solution {
    
public:
    int maxDistToClosest(vector<int>& seats) {
    
        int n=seats.size();
        int first,pre,last;//记录最左边的有人的座位、上一个有人的座位、最后一个有人的座位
        int maxInterval=INT_MIN;//记录两个座位之间最大间距
        int count=0;
        for(int i=0;i<n;i++){
    
            if(seats[i]==1){
    
                if(count==0){
    //如果是第一个有人的座位
                    first=i;
                    last=i;
                }else if(count>=1){
    //如果是第一个以后 有人的座位
                    pre=last;
                    last=i;
                    maxInterval=max(maxInterval,last-pre);//保存当前有人的座位和上一个有人的座位 的 最大间距
                }
                count++;
            }
        }
        return max({
    first,n-1-last,maxInterval/2});//选择最大值

    }
};