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

小灰灰 2022-05-18 11:11 123阅读 0赞

在一排座位（ `seats`）中，`1` 代表有人坐在座位上，`0` 代表座位上是空的。

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

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

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

**示例 1：**

输入：[1,0,0,0,1,0,1]
    输出：2
    解释：
    如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
    如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
    因此，他到离他最近的人的最大距离是 2 。

**示例 2：**

输入：[1,0,0,0]
    输出：3
    解释： 
    如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
    这是可能的最大距离，所以答案是 3 。

**提示：**

1.  `1 <= seats.length <= 20000`
2.  `seats` 中只含有 0 和 1，至少有一个 `0`，且至少有一个 `1`。

--------------------

思路：遍历数组，找到空座位的索引，然后找到距离该空座位最近的有人坐的座位，并求出距离，更新最大距离。

class Solution {
        public int maxDistToClosest(int[] seats) {
            int max=0;  //最大距离
    	    for(int i=0;i<seats.length;i++) {
    	    	if(seats[i]==0) {
    	    		int minD=getMinDistance(seats,i);
    	    		int t=Math.abs(minD-i);
    	    		if(t>max) {
    	    			max=t;
    	    		}
    	    	}
    	    }
        	return max;
        }
         public  int getMinDistance(int[] seats,int k) {
        	int leftIndex=k; //向左移动的指针
        	int rightIndex=k;
        	while(leftIndex>=0&&rightIndex<seats.length) {
        		if(seats[leftIndex]==1) {
        			return leftIndex;
        		}
        		if(seats[rightIndex]==1) {
        			return rightIndex;
        		}
        		leftIndex--;
        		rightIndex++;
        	}
        	while(leftIndex>=0) {
        		if(seats[leftIndex]==1) {
        			return leftIndex;
        		}
        		leftIndex--;
        	}
        	while(rightIndex<seats.length) {
        		if(seats[rightIndex]==1) {
        			return rightIndex;
        		}
        		rightIndex++;
        	}
        	return 0;
        }
    }