Medium

题目描述

给你一个数组，表示一排座位，其中 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
解释：
如果亚历克斯坐在最后一个座位（seats[3]）上，他离最近的人有 3 个座位远。
这是可能的最大距离，所以答案是 3 。

示例 3：

输入：seats = [0,1]
输出：1

提示：

  • 2 <= seats.length <= 2 * 10^4
  • seats[i] 为 0 或 1
  • 至少有一个座位是空的
  • 至少有一个座位是被占的

解题思路

这道题需要找到空座位中到最近有人座位的最大距离。我们可以分三种情况考虑：

  1. 左端连续空座位：如果开头有连续空座位，亚历克斯坐在最左端，距离最近的人的距离就是到第一个人的距离。

  2. 右端连续空座位：如果结尾有连续空座位，亚历克斯坐在最右端，距离最近的人的距离就是到最后一个人的距离。

  3. 中间连续空座位：如果两个人之间有连续空座位，亚历克斯坐在中间位置能获得最大距离，这个距离是空座位段长度的一半（向下取整）。

算法步骤：

  • 遍历数组，找出所有连续的空座位段
  • 对于开头和结尾的空座位段，距离等于段长度
  • 对于中间的空座位段，最优距离是 (段长度 + 1) / 2
  • 返回所有情况中的最大值

这种方法只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int n = seats.size();
        int maxDist = 0;
        int left = -1;
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (left == -1) {
                    // 左端空座位
                    maxDist = max(maxDist, i);
                } else {
                    // 中间空座位
                    maxDist = max(maxDist, (i - left) / 2);
                }
                left = i;
            }
        }
        
        // 右端空座位
        maxDist = max(maxDist, n - 1 - left);
        
        return maxDist;
    }
};

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        max_dist = 0
        left = -1
        
        for i in range(n):
            if seats[i] == 1:
                if left == -1:
                    # 左端空座位
                    max_dist = max(max_dist, i)
                else:
                    # 中间空座位
                    max_dist = max(max_dist, (i - left) // 2)
                left = i
        
        # 右端空座位
        max_dist = max(max_dist, n - 1 - left)
        
        return max_dist

public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int n = seats.Length;
        int maxDist = 0;
        int left = -1;
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (left == -1) {
                    // 左端空座位
                    maxDist = Math.Max(maxDist, i);
                } else {
                    // 中间空座位
                    maxDist = Math.Max(maxDist, (i - left) / 2);
                }
                left = i;
            }
        }
        
        // 右端空座位
        maxDist = Math.Max(maxDist, n - 1 - left);
        
        return maxDist;
    }
}

/**
 * @param {number[]} seats
 * @return {number}
 */
var maxDistToClosest = function(seats) {
    const n = seats.length;
    let maxDist = 0;
    let left = -1;
    
    for (let i = 0; i < n; i++) {
        if (seats[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用常数额外空间

相关题目