0849-到最近的人的最大距离

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

给你一个数组 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
  • 至少有一个 空座位
  • 至少有一个 座位上有人

方法一：双指针 + 贪心

思路与算法

题目给出一个下标从 0 开始，长度为 n 的数组 seats，其中 seats}[i] = 1 表示有人坐在第 i 个位置上，在该题解中我们称之为「有人座位」，seats}[i] = 0 表示第 i 个座位为空，称之为「无人座位」，并且题目数据保证至少有一个「有人座位」和「无人座位」。现在我们需要找到一个「无人座位」使得该位置与距离该位置最近的「有人位置」之间的距离最大，并返回该值。

首先假设已经确定了我们所选择的「无人座位」i 的左和右离它最近的「有人座位」分别为座位 l 和 r，0 \le l < i < r < n。那么此时座位 i 的离其位置最近的人的距离

d_{min} = \min{i - l, r - i} \le \lfloor r - l}{2} \rfloor

其中当 i = \lfloor l + r}{2} \rfloor 时取到等号。所以对于两个相邻的「有人座位」，我们在中间就坐一定是最优的。因此我们可以用「双指针」来找到每一对相邻的有人座位，并计算若在其中间就坐能得到的最大间隔距离。

以上的讨论是建立在我们选择的「无人座位」的左右都存在「有人座位」的情况。对于边缘的「无人座位」，即其某一侧不存在「有人座位」：

  • 若左边存在边缘的「无人座位」，则此时为了使距离其最近的右边的「有人座位」最远，我们应该尽可能的往左边坐，即坐在第一个位置。
  • 若右边存在边缘的「无人座位」，则此时为了使距离其最近的左边的「有人座位」最远，我们应该尽可能的往右边坐，即坐在第最后一个位置。

最后返回全部情况中能得到的最大距离即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int res = 0;
        int l = 0;
        while (l < seats.size() && seats[l] == 0) {
            ++l;
        }
        res = max(res, l);
        while (l < seats.size()) {
            int r = l + 1;
            while (r < seats.size() && seats[r] == 0) {
                ++r;
            }
            if (r == seats.size()) {
                res = max(res, r - l - 1);
            } else {
                res = max(res, (r - l) / 2);
            }
            l = r;
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxDistToClosest(int[] seats) {
        int res = 0;
        int l = 0;
        while (l < seats.length && seats[l] == 0) {
            ++l;
        }
        res = Math.max(res, l);
        while (l < seats.length) {
            int r = l + 1;
            while (r < seats.length && seats[r] == 0) {
                ++r;
            }
            if (r == seats.length) {
                res = Math.max(res, r - l - 1);
            } else {
                res = Math.max(res, (r - l) / 2);
            }
            l = r;
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int res = 0;
        int l = 0;
        while (l < seats.Length && seats[l] == 0) {
            ++l;
        }
        res = Math.Max(res, l);
        while (l < seats.Length) {
            int r = l + 1;
            while (r < seats.Length && seats[r] == 0) {
                ++r;
            }
            if (r == seats.Length) {
                res = Math.Max(res, r - l - 1);
            } else {
                res = Math.Max(res, (r - l) / 2);
            }
            l = r;
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maxDistToClosest(int* seats, int seatsSize) {
    int res = 0, l = 0;
    while (l < seatsSize && seats[l] == 0) {
        ++l;
    }
    res = fmax(res, l);
    while (l < seatsSize) {
        int r = l + 1;
        while (r < seatsSize && seats[r] == 0) {
            ++r;
        }
        if (r == seatsSize) {
            res = fmax(res, r - l - 1);
        } else {
            res = fmax(res, (r - l) / 2);
        }
        l = r;
    }
    return res;
}
[sol1-Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        res, l = 0, 0
        while l < len(seats) and seats[l] == 0:
            l += 1
        res = max(res, l)
        while l < len(seats):
            r = l + 1
            while r < len(seats) and seats[r] == 0:
                r += 1
            if r == len(seats):
                res = max(res, r - l - 1)
            else:
                res = max(res, (r - l) // 2)
            l = r
        return res
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maxDistToClosest(seats []int) int {
    res := 0
    l := 0
    for l < len(seats) && seats[l] == 0 {
        l++
    }
    res = max(res, l)
    for l < len(seats) {
        r := l + 1
        for r < len(seats) && seats[r] == 0 {
            r++
        }
        if r == len(seats) {
            res = max(res, r - l - 1)
        } else {
            res = max(res, (r - l) / 2)
        }
        l = r
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var maxDistToClosest = function(seats) {
    let res = 0, l = 0;
    while (l < seats.length && seats[l] === 0) {
        l++;
    }
    res = Math.max(res, l);
    while (l < seats.length) {
        let r = l + 1;
        while (r < seats.length && seats[r] === 0) {
            r++;
        }
        if (r === seats.length) {
            res = Math.max(res, r - l - 1);
        } else {
            res = Math.max(res, parseInt((r - l) / 2));
        }
        l = r;
    }
    return res;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 seats 的长度。
  • 空间复杂度：O(1)，仅使用常量空间。
 Comments
On this page
0849-到最近的人的最大距离