leetcode-849-到最近的人的最大距离
leetcode-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 <= seats.length <= 20000seats中只含有 0 和 1，至少有一个0，且至少有一个1。
要完成的函数：
int maxDistToClosest(vector<int>& seats)
说明：
1.这道题给了一个vector，里面存放着0和1，1表示这个位置有人，0表示没人。现在亚力克斯想坐在一个离最近的人距离最远的座位上，也就是“四周最空旷”的座位。
2.我们之前做过一道跟这道题类似的题目，我们只需做两次循环，一次把所有0的位置跟左边的1比较，得到跟左边的最近的1的位置距离。再跟右边的1比较，得到跟右边的最近的1的位置距离。
每个数都能得到两个位置距离，一个跟左边最近的1比较，一个跟右边最近的1比较，除了最开始的1的左边的数，比如[0,0,1,1]中第一个0和第二个0，只有跟右边的1比较得到的位置距离，还有最后面的1的右边的数，比如[1,1,0,0]中的两个0，只有跟左边的1比较得到的位置距离。
我们得到的两个位置距离，取小的那个。
把每个原本0值对应的得到的位置距离，存在vector中。
最后遍历一遍这个vector，得到最大的位置距离，返回。
在实际代码实现中，我们还可以简化步骤，降低时间复杂度和空间复杂度，代码如下：（附详解）
int maxDistToClosest(vector<int>& seats)
{
int left,right,s1=seats.size(),max1;
for(left=0;left<s1;left++)//left表示最左边的第一个1的位置
{
if(seats[left]==1)
break;
}
for(int i=left+1;i<s1;i++)//从left的下一位开始，逐个计算跟左边最近的1的距离
{
if(seats[i]==1)//不断更新左边最近的1的位置
left=i;
else//把距离存储在原本的vector中，为了避免混乱，以负数（相反数）的形式存储
seats[i]=-(i-left);
}
for(right=s1-1;right>=0;right--)//right表示最右边的第一个1的位置
{
if(seats[right]==1)
break;
}
if(right!=s1-1)//如果最右边的第一个1不是最后一位，也就是right的右边还有0
max1=-seats[s1-1];//那么max1初始化为……
else//如果右边的第一个1在最后一位，也就是right的右边没有0了
max1=0;//那么max1初始化为0
for(int i=right-1;i>=0;i--)//从right的前一位开始，逐个计算跟右边最近的1的距离
{
if(seats[i]==1)
right=i;
else if(seats[i]==0)//应对[0,0,1,1,0,0,0]这种情况中的前两个0
{
max1=max(max1,right-i);
}
else//正常情况下 夹在两个1中间的情况
{
seats[i]=max(-(right-i),seats[i]);
max1=max(max1,-seats[i]);
}
}
return max1;
}上述代码可能注释也还解释得不是十分清楚。
我们通过跟左边最近的1和右边最近的1的位置比较，得到位置距离，存储在原本的vector中。
存储的时候，为了避免跟原本的1混乱了，存储成负数（相反数）的形式。
我们最后还需要遍历一遍vector，得到最大的位置距离。
但笔者为了省时间，把最后这一步融合在代码中最后的for循环中了，跟右边最近的1比较完之后，得到的数值再跟vector中存储的数值比较，只剩下一个数，然后不断更新最大的位置距离。
为了实现这一点，我们需要考虑最开始max1要初始化为多少。
还不懂的同学自己手推一遍代码，理清过程就清楚啦！
上述代码实测12ms，beats 100% of cpp submission。