JZX轻语：简
LeetCode 849 - 到最近的人的最大距离
发表于2024年05月15日
一般这种考虑左右两侧的数组题目(如845)，都可以通过两次遍历(从左，从右)+前缀和思路维护局部数据，然后再遍历一次数组以组成结果。在这个题目中，这个局部数据就是左侧/右侧连续为0的个数，最后再遍历数组，其中第i个座位距离最近有人座位的距离为min(左侧连续为0的个数, 右侧连续为0的个数)。需要注意左/右侧没人的情况。
此外，这种双侧题目，可以使用双指针+贪心的方式以减少空间开销。使用left和right从左到右分别指向有人座位，其中right为left右侧的第一个有人座位(即left下一次会指向right)。因此，这两个有人座位的空隙中，最大的距离为(right - left) // 2。不断移动两个指针，直至right滑出数组即可。同样需要留意数组边缘左右侧没人的情况。
使用前缀和思路：
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
# 统计左右两侧连续为0的次数
left_dis = [-1] * len(seats)
right_dis = [-1] * len(seats)
for i in range(len(seats)):
if seats[i] == 1:
left_dis[i] = 0
else:
if i > 0 and left_dis[i - 1] != -1:
left_dis[i] = left_dis[i - 1] + 1
for i in range(len(seats) - 1, -1, -1):
if seats[i] == 1:
right_dis[i] = 0
else:
if i + 1 < len(seats) and right_dis[i + 1] != -1:
right_dis[i] = right_dis[i + 1] + 1
# 遍历数组，找到（左右两侧连续为0次数最小者）最大的元素
ans = 0
for i in range(len(seats)):
dis = left_dis[i]
# 注意边缘情况, left_dis[i] == -1会发生在左侧没人的情况, right_dis同理
if dis == -1 or dis > right_dis[i] != -1:
dis = right_dis[i]
ans = max(dis, ans)
return ans使用双指针的思路：
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
left = -1
right = 0
# right先滑向第一个有人座位
while right < len(seats) and seats[right] == 0:
right += 1
ans = right # 初始化结果为right, 即坐在最左侧
while right < len(seats):
left, right = right, right + 1
while right < len(seats) and seats[right] == 0:
right += 1
# 如果right已经滑向了数组末尾, 此时坐在最右侧为该间隙内最远的距离
max_dis = (right - left) // 2 if right != len(seats) else right - left - 1
ans = max(ans, max_dis)
return ans