问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3754 访问。
在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
至少有一个空座位，且至少有一人坐在座位上。
亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
返回他到离他最近的人的最大距离。
提示：
1 <= seats.length <= 20000
seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
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.
Note:
1 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3754 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 1, 1, 0, 0, 0, 1, 0 };
var res = MaxDistToClosest(nums);
Console.WriteLine(res);
nums = new int[] { 1, 0, 0, 0 };
res = MaxDistToClosest2(nums);
Console.WriteLine(res);
Console.ReadKey();
}
private static int MaxDistToClosest(int[] seats) {
//直接解法
int left, right;
int min = int.MaxValue;
int max = int.MinValue;
for(int i = 0; i < seats.Length; i++) {
if(seats[i] == 0) {
//双指针找0，即空座位
left = i; right = i;
while(--left >= 0 && seats[left] == 0) { }
while(++right <= seats.Length - 1 && seats[right] == 0) { }
//处理好边界
if(left == -1) left = int.MaxValue;
if(right == seats.Length) right = int.MaxValue;
//分析到最近的人的最大距离
if(i - left < right - i && i - left >= 0) {
min = i - left;
} else {
min = right - i;
}
//最大距离
max = Math.Max(max, min);
}
}
//返回最大距离
return max;
}
private static int MaxDistToClosest2(int[] seats) {
//记录所有非空座位
var indexOfOne = new List<int>();
for(var i = 0; i < seats.Length; i++) {
if(seats[i] == 0) continue;
indexOfOne.Add(i);
}
//找到2个非空座位的中间座位
var max = indexOfOne[0];
for(int i = 0, j = 1; i < indexOfOne.Count && j < indexOfOne.Count; i++, j++) {
var halfLength = (indexOfOne[j] - indexOfOne[i]) / 2;
if(halfLength > max) max = halfLength;
}
//处理边界
var length = seats.Length - 1 - indexOfOne[indexOfOne.Count - 1];
if(length > max) max = length;
//返回最大距离
return max;
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3754 访问。
2
3分析：
显而易见，以上2种算法的时间复杂度均为： 。