题目:
题解:
(一)直接搜索:
<1>遍历一次seats数组,找到所有空座位对应编号保存在empty数组,非空座位编号保存在notempty数组
<2>对每个空座位进行搜索,将其他已经有人的座位与该座位距离保存在dis中,找到最小距离mindis,更新maxdis
def maxDistToClosest(self, seats):
lenseats = len(seats)
empty = []
notempty = []
maxdis = float("-inf")
for i in range(lenseats):
if seats[i]==0:
empty.append(i)
else:
notempty.append(i)
for j in range(len(empty)):
dis = []
for k in range(len(notempty)):
dis.append(abs(empty[j]-notempty[k]))
mindis = min(dis)
maxdis = max(maxdis,mindis)
return maxdis
测试结果通过,但提交超时了:
(二)参考https://www.jianshu.com/p/6f1e8121e780
亚历克斯可以坐的位置的距离分三种情况:
<1>左边有座位为空,坐在第一个位置,最小距离为第一个人坐的位置
<2>右边有空位,坐在最后一个位置,最小距离为与最右边有人的座位的距离
<3>左右两端都没有空位,只能坐在两个有人的座位之间,坐在两人最中间的位置会使最小距离最大化
最终可以得到的最大化的最小距离是以上三种情况的最大值
class Solution(object):
def maxDistToClosest(self, seats):
lenseats = len(seats)
person = []
for i in range(lenseats):
if seats[i]==1:
person.append(i)
dis1 = person[0]
dis2 = lenseats-person[-1]-1
dis3 = 0
for j in range(len(person)-1):
dis3 = max(int(abs(person[j]-person[j+1])//2),dis3)
maxdis = max(dis1,dis2,dis3)
return maxdis