一 🏠 题目描述
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 * 104seats[i] 为 0 或 1
至少有一个 空座位
至少有一个 座位上有人
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的，至少有一个空座位，且至少有一人已经坐在座位上。找到一个能够使离最近的人距离最大化的座位 🌺🌺🌺
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
分类讨论法：对于 seats 中 一段 [X1 , X2] 距离（ X1，X2 表示两个已占座位且不为左右两端）
若 X2 - X1 + 1 可以整除 2 ，则离最近人最大化距离为 X2 (X2 - X1 + 1) / 2
若 X2 - X1 + 1 不可以整除 2 则离最近人最大化距离为 (X2 - X1 + 1) / 2 + 1 🌷🌷🌷
那么对于两端 [ 0 , x ] 和 [ x , end ] （ x 表示已占座位）
[ 0 , x ] ，离最近人最大化距离为 x [ x , end ]，离最近人最大化距离为 end - x 🐌🐌🐌
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
int maxDistToClosest(std::vector<int>& seats) { int maxDist =0, currentDist =0, len = seats.size(); //初始化最大距离, 当前距离, 数组长度 for (int i =0; i < len; i++) { //遍历输入数组 if (seats[i] ==0) { //若当前座位为空 ++currentDist; //则当前距离加加 continue; //继续循环 } if (currentDist - i !=0) { //不是最左端 if (currentDist % 2==0) currentDist = currentDist / 2; //可以整除 2else currentDist = currentDist / 2+1; //不可以整除 2 } maxDist = std::max(maxDist, currentDist); //把最大距离赋值给 maxDist currentDist =0; //赋值后将 currentDist 清零 } if (seats[len -1] ==0) maxDist = std::max(maxDist, currentDist); //处理0结尾的情况 return maxDist; //返回最大距离 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
if (currentDist - i !=0) { //不是最左端 if (currentDist % 2==0) currentDist = currentDist / 2; //可以整除 2else currentDist = currentDist / 2+1; //不可以整除 2}
if 分支内的判断对应着
若 X2 - X1 + 1 可以整除 2 ，则离最近人最大化距离为 X2 (X2 - X1 + 1) / 2
若 X2 - X1 + 1 不可以整除 2 则离最近人最大化距离为 (X2 - X1 + 1) / 2 + 1 🐳🐳🐳
if (currentDist - i !=0) ... //不是最左端 maxDist = std::max(maxDist, currentDist); //把最大距离赋值给 maxDist
这里若 currentDist - i == 0 ，则对应着 [ 0 , x ] ，离最近人最大化距离为 x 🐌🐌🐌
if (seats[len -1] ==0) maxDist = std::max(maxDist, currentDist); //处理0结尾的情况
最后的分支判断对应着 [ x , end ]，离最近人最大化距离为 end - x
官网解答与该法效率接近，但不易理解，故不赘述，如感兴趣可自行查阅 🌼🌼🌼
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理没有问题（上述实现和题解博主原创）
