2022/01/16 - 849. Maximize Distance to Closest Person

849. Maximize Distance to Closest Person - Medium

Description

849. Maximize Distance to Closest Person

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to the closest person.

题目的大致意思就是有一个数组代表座位，seats[i]的值是1时说明座位上有人，值为0时说明这个位置没有人，可以坐。让我们找出一个离最近的人距离最远的座位。

Solution

首先想要找出距离最近的人最远的位置，就有三种情况：

1. 左右两边都有人
2. 右边没有人，只有左边有人
3. 左边没有人，只有右边有人

对于第一种情况我们就需要双指针来解决这个问题，一个代表左边有人的位置的索引，遍历到右边有人的位置的索引时，(右边有人的座位的索引 - 左边有人的座位的索引) / 2，就是这两个人之间距离最近的那个人的距离。

对于第二种和第三种情况，我们就要单独拿出来说。举个例子，假如seats数组是这样的：[1,0,0,0,0,0,0,0,...,0]，那么我们就用 数组的长度 - 左边有人座位的索引 - 1，就能得出第二种情况的答案。而对于第三种情况：[0,0,0,0,0,...,0,1]，我们就直接用最后一个有人座位的索引当作距离就行。

分析完题目，我们就能写出代码了：

class Solution {
    public int maxDistToClosest(int[] seats) {
        int p1 = -1, n = seats.length, res = 0;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                // p1小于零时，就是第三种情况，我们直接取i就可以
                res = p1 < 0 ? i : Math.max(res, (i - p1) / 2);
                p1 = i;
            }
        }
        // 判断一下第二种情况
        res = Math.max(res, n - p1 - 1);
        return res;
    }
}

评论