2023年8月22日每日一题--849. 到最近的人的最大距离

leetcode链接：849. 到最近的人的最大距离

题目分析

方案一

class Solution {
    public int maxDistToClosest(int[] seats) {
        int result = 1;

        int index = -1;

        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1) { // 当我遇见诱人的时候，我才做出改变
                if (index == -1) { // 第一个位置没人的时候，我需要一下特殊的照顾
                    result = Math.max(result, i);
                } else {
                    result = Math.max(result, (i - index) / 2); // 此时我的左右都有人
                }
                index = i;
            } 
        }
        result = Math.max(result, seats.length - 1 - index); // 特殊判断，最后一个没人怎么办。

        return result;
    }
}

结果

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

官方题解

官方的题解还不如方案一的方法简洁。

https://leetcode.cn/problems/maximize-distance-to-closest-person/solutions/2393766/dao-zui-jin-de-ren-de-zui-da-ju-chi-by-l-zboe/

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/maximize-distance-to-closest-person/solutions/2393766/dao-zui-jin-de-ren-de-zui-da-ju-chi-by-l-zboe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。