这是悦乐书的第328次更新，第351篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第198题（顺位题号是849）。在一排座位中，1表示一个人坐在该座位上，0表示座位是空的。在这些座位中，至少有一个空座位，至少有一个人坐着。Alex想坐在座位上，以便他和离他最近的人之间的距离最远。返回距离最近的人的最大距离。例如：
输入：[1,0,0,0,1,0,1]
输出：2
说明：如果Alex坐在第二个空座位（seats[2]），那么离最近的人距离为2。如果Alex坐在任何其他空座位上，则离最近的人的距离为1。因此，到最近的人的最大距离是2。
输入：[1,0,0,0]
输出：3
说明：如果Alex坐在最后一个座位上，那么离他最近的人距离为3。这是可能的最大距离，所以答案是3。
注意：
-
1 <= seats.length <= 20000
-
所有座位中仅包含0或1，至少一个0，至少一个1。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 解题
在解题前，先来看看题目的意思。Alex想要在一排座位中，找到一个离人最近但是距离最远的座位，题目通过一个数组来表示一排座位，元素值为0表示当前这个座位是空的，Alex可以坐，为1时表示当前这个座位有人坐了，Alex不能坐，也就是说，在为0的座位中，要找一个离最近的人距离越远越好的座位。我们可以分三种情况来选座位：
（1）左边是墙时，即数组中第一个元素是0，或者数组前部分是连续的0，如果往右，至少会遇到一个座位上有人，此时Alex离这个人是最近的，距离也是最远的。比如数组{0,0,0,1}，Alex坐在第一个座位上，离他最近的人的最远距离是3。
（2）左右两边都有人时，即此时数组中出现了一段连续的0，也就是有连续好几个连着的空座位可以选，此时Alex坐在这些连续空座位的中间是最好的，离左右两边的人最近，距离也是相等的。比如数组{1,0,0,0,1}，Alex坐在第三个座位上，即坐在seats[2]上，距离两边的人都是最近的，且距离最大，都为2。
（3）右边是墙时，即数组中最后一个元素是0，或者后部分是连续的0，如果往左，至少会遇到一个座位上有人，此时Alex离这个人是最近的，距离也是最远的。比如数组{1,0,0,0}，Alex坐在第四个座位上，离他最近的人的最远距离是3。
通过上面的分析，我们可以使用一个变量记录前一个座位已经被坐的索引，再根据当前座位来判断，看属于上面三种情况中的哪一种，计算距离，比较最大值，通过双指针来实现。
注意，计算距离是计算索引之差。
public int maxDistToClosest(int[] seats) {
int left = -1, n = seats.length;
int maxDistance = 0;
for (int i=0; i<n; i++) {
if (seats[i] == 0) {
continue;
}
if (left == -1) {
// 左边第一位是1或者连续的0，有可能左边靠墙
maxDistance = Math.max(maxDistance, i);
} else {
// 中间部分连续的0，即中间
maxDistance = Math.max(maxDistance, (i-left)/2);
}
left = i;
}
// 结束部分为连续的0，即右边靠墙
if (seats[n-1] == 0) {
maxDistance = Math.max(maxDistance, n-1-left);
}
return maxDistance;
}
03 小结
算法专题目前已日更超过五个月，算法题文章198+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论