到最近的人最大距离
在一排座位( 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 <= 20000
seats
中只含有0
和1
,至少有一个0
,且至少有一个1
。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximize-distance-to-closest-person
解题思路
将连续空座计算出来,然后不断的求最大值就行,最大的需要
PHP 实现
$seats = explode('1', implode('', $seats));
$res = 0;
foreach ($seats as $key => $val) {
if ($key == 0 || $key == count($seats) - 1) {
$res = max($res, strlen($val));
} else {
$res = max($res, ceil(strlen($val) / 2));
}
}
return $res;
Go 实现 来源于 梦康群群友- 我要割麦子
func maxDistToClosest(seats []int) int {
var (
max1 int
max2 int
max3 int
)
dp := make([]int, len(seats))
pre := 0
diff := 0
for i,v := range seats {
if v == 1 {
dp[i] = i - pre
pre = i
}else{
dp[i] = i - pre
}
diff = max(dp[i], diff)
}
for i,v := range seats {
if v == 1 {
max1 = i
break
}
}
for i := len(seats) - 1;i >= 0;i-- {
if seats[i] == 1 {
max2 = len(seats) - i - 1
break
}
}
max3 = max(max1, max2)
// fmt.Println(diff)
max3 = max(max3, int(diff / 2))
return max3
}
func max(a,b int) int {
if a >= b {
return a
}
return b
}
© 原创文章