Leetcode-849: maximum distance to the nearest person

subject

Topic linking

Give you an array seats Indicates a row of seats , among seats[i] = 1 It means someone is sitting on the i In one seat ,seats[i] = 0 Delegate seat i The is empty （ Subscript from 0 Start ）.

There is at least one empty seat , There is at least one person sitting in the seat .

Alex wants to be in a seat that maximizes the distance between him and the person closest to him .

Return to his maximum distance to the nearest person .

Example 1：

 Input ：seats = [1,0,0,0,1,0,1]
 Output ：2
 explain ：
 If Alex is in the second seat （seats[2]） On , The distance from him to the nearest person is  2 .
 If Alex is sitting in any other empty seat , The distance from him to the nearest person is  1 .
 therefore , The biggest distance he can get to the nearest person is  2 . 

Example 2：

 Input ：seats = [1,0,0,0]
 Output ：3
 explain ：
 If Alex is in the last seat , He is the nearest person  3  Seats away .
 This is the maximum distance possible , So the answer is  3 .

Example 3：

 Input ：seats = [0,1]
 Output ：1

Problem solving

Method 1 ： One traverse

There are three situations

• 1. Calculate the distance from the first person on the left to the first person on the left （ Alex can sit on the far left ）
• 2. Calculate the distance from the rightmost position with people to the last position （ Alex can sit on the far right ）
• 3. Calculate the distance between two manned positions （ Alex can sit between two people ）

Take the maximum of these three cases .

class Solution {
    
public:
    int maxDistToClosest(vector<int>& seats) {
    
        int n=seats.size();
        int first,pre,last;// Record the left most seat 、 The last seat is occupied 、 The last seat is occupied 
        int maxInterval=INT_MIN;// Record the maximum distance between two seats 
        int count=0;
        for(int i=0;i<n;i++){
    
            if(seats[i]==1){
    
                if(count==0){
    // If it is the first seat with people 
                    first=i;
                    last=i;
                }else if(count>=1){
    // If it is after the first   Occupied seat 
                    pre=last;
                    last=i;
                    maxInterval=max(maxInterval,last-pre);// Save the currently occupied seat and the last occupied seat   Of   Maximum spacing 
                }
                count++;
            }
        }
        return max({
    first,n-1-last,maxInterval/2});// Select the maximum value 

    }
};