Leetcode每日一题：849. 到最近的人的最大距离（2023.8.22 C++）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode每日一题：849. 到最近的人的最大距离（2023.8.22 C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

题目描述：

实现代码与解析：

双指针

原理思路：

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

题目描述：

给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。

至少有一个空座位，且至少有一人已经坐在座位上。

亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。

返回他到离他最近的人的最大距离。

示例 1：

Leetcode每日一题：849. 到最近的人的最大距离（2023.8.22 C++）,Leetcode,leetcode,c++,算法

输入：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
至少有一个 空座位
至少有一个 座位上有人

实现代码与解析：

双指针

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;
    }
};