目录
849. 到最近的人的最大距离
题目描述:
实现代码与解析:
双指针
原理思路:
849. 到最近的人的最大距离
题目描述:
给你一个数组 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
提示:文章来源:https://www.toymoban.com/news/detail-672382.html
2 <= seats.length <= 2 * 104
-
seats[i]
为0
或1
- 至少有一个 空座位
- 至少有一个 座位上有人
实现代码与解析:
双指针
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int res = 0;
int l = 0;
while(l < seats.size() && seats[l] == 0) l++; // 第一个非0
res = max(res, l); // 算一下最左侧距离
while(l < seats.size())
{
int r = l + 1;
while(r < seats.size() && seats[r] == 0) r++; // i 后第一个非0
if (r == seats.size()) res = max(res, r - l - 1); // 如果是最后一个,算一下与右侧的距离
else res = max(res, (r - l) >> 1); // 不是最后一个,那么最大距离是其之间的距离除2
l = r; // 计算下一个区间
}
return res;
}
};
原理思路:
简单题,双指针,每个区间的最大距离就是两个非0区间差值的一半,不过左右两侧不一定有1,单独处理一下即可。文章来源地址https://www.toymoban.com/news/detail-672382.html
到了这里,关于Leetcode每日一题:849. 到最近的人的最大距离(2023.8.22 C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!