849.到最近的人的最大距离

【LetMeFly】849.到最近的人的最大距离

力扣题目链接：https://leetcode.cn/problems/maximize-distance-to-closest-person/

给你一个数组 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 * 104
• seats[i] 为 0 或 1
• 至少有一个 空座位
• 至少有一个 座位上有人

方法一：遍历

一共分为三种情况：

1. 坐最左边
2. 尽可能坐两人中间
3. 坐最右边

遍历一遍，取一个最大值即可。

• 时间复杂度$O(len(seats))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int ans=1;
        int lastSeat = -1;
        for (int i = 0; i < seats.size(); i++) {
            if (seats[i]) {
                if (lastSeat == -1) {  // 首次
                    ans = max(ans, i);
                }
                else {
                    ans = max(ans, (i - lastSeat) / 2);
                }
                lastSeat = i;
            }
        }
        ans = max(ans, (int)seats.size() - lastSeat - 1);
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        ans = 1
        lastSeat = -1
        for i in range(len(seats)):
            if seats[i]:
                if lastSeat == -1:
                    ans = max(ans, i)
                else:
                    ans = max(ans, (i - lastSeat) // 2)
                lastSeat = i
        ans = max(ans, len(seats) - lastSeat - 1)
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132420545