LeetCode 849. Maximize Distance

题目

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.
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 closest person.

Example 1:
Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:
Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:
1 <= seats.length <= 20000 seats contains only 0s or 1s, at least one 0, and at least one 1.

解析

题目求的是距离最近的人距离的最大值，即最近距离的人和距离的最大值。
因此可以得到一个简单的方法来计算，计算相离两个人的距离最大值除2即可，但是要考虑到开始为0和结尾为0的情况。
另外一种方法是从网上得知，先生成left和right数组，初始化为数组长度，然后1的位置置0，0的位置置其前一项加1，从右往左亦然。最后求left和right数组相比的最小值，再求最小值中的最大值即为答案。
第二种方法比较绕，但是其正是求解最近距离的人，和该距离的最大值。

代码（C语言）

解法1：

int maxDistance(int dis1, int dis2);
int maxDistToClosest(int* seats, int seatsSize) {
    int maxDist = 0, zeroLens = 0;
    
    for (int i = 0; i < seatsSize; ++i) {
        if (seats[i] == 0)
            ++zeroLens;
        else
            zeroLens = 0;
        
        maxDist = maxDistance(maxDist, (zeroLens + 1) / 2);
    }
    
    // begin with 0, end with 0
    for (int i = 0; i < seatsSize; ++i) {
        if (seats[i] == 1) {
            maxDist = maxDistance(maxDist, i);
            
            break;
        }
    }
    for (int i = seatsSize - 1; i >= 0; --i) {
        if (seats[i] == 1) {
            maxDist = maxDistance(maxDist, seatsSize - i - 1);
            
            break;
        }
    }
    
    return maxDist;
}

int maxDistance(int dis1, int dis2) {
    return dis1 > dis2 ? dis1 : dis2;
}

解法1求解的是最多的0的个数/2，和开始为0，结尾为0的结果做比较。
解法2：

int minDistance(int dis1, int dis2) {
    return dis1 > dis2 ? dis2 : dis1;
}

int maxDistToClosest2(int* seats, int seatsSize) {
    if (seatsSize == 0)
        return 0;
    
    int* leftCountArr = (int*)malloc(seatsSize * sizeof(int));
    int* rightCountArr = (int*)malloc(seatsSize * sizeof(int));
    
    // initialize
    for (int i = 0; i < seatsSize; ++i) {
        leftCountArr[i] = seatsSize;
        rightCountArr[i] = seatsSize;
    }
    
    // left and right arr
    for (int i = 0; i < seatsSize; ++i) {
        if (seats[i] == 1) {
            leftCountArr[i] = 0;
        } else {
            if (i > 0) {
                leftCountArr[i] = leftCountArr[i - 1] + 1;
            }
        }
    }
    
    for (int i = seatsSize - 1; i >= 0; --i) {
        if (seats[i] == 1) {
            rightCountArr[i] = 0;
        } else {
            if (i < seatsSize - 1) {
                rightCountArr[i] = rightCountArr[i + 1] + 1;
            }
        }
    }
    
    int maxDis = 0;
    for (int i = 0; i < seatsSize; ++i) {
        if (seats[i] == 0) {
            maxDis = maxDistance(maxDis,
                                 minDistance(leftCountArr[i], rightCountArr[i]));
        }
    }
    
    free(leftCountArr);
    free(rightCountArr);
    
    return maxDis;
}

解法2中，执行了上述的思路，最后先求最小(closest)，再求最大(max)。
上述两种方法均accepted，请读者查阅。