来源：LeetCode
难度：中等
描述：
给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。至少有一个空座位，且至少有一人已经坐在座位上。亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。返回他到离他最近的人的最大距离。
题意：题目稀里哗啦一大堆其实用人话来说就是将数组比成座位，1代表有人坐，0代表没人坐，现在想在这些没人坐的地方（为0）挑一个坐下来，要求这个位置是所有没人坐的位置中里同时离两边的人最远的，并且让咱们求出这个最远距离…
题外话：忍不住吐槽一下，这题目看起来真是难以理解，得亏有示例…
分析：这是一个求全局最优解的题目，自然可以用动态规划来解；同样，咱们也可以采用数学方式来解：数连续的0的个数，两端的0直接计数，两人中间的0计数则需打折扣，下面是具体内容
解题
方法一：动态规划法解题
思路：构造两个和元素组等长的数组left和right，其中left装每个0和左边1最近的距离，right装每个0和右边1最近的距离，如果元素是1，则距离为0
举个例子：令 left[i] 为座位 i 到坐在 i 左边的人的最近距离。同理 right[i] 为座位 i 到坐在 i 右边的人的最近距离。那么该座位到最近的人的距离为 min(left[i], right[i])
代码：
1public int maxDistToClosest(int[] seats) {
2 int N = seats.length;
3 //构造等大的两个数组 left,right
4 int[] left = new int[N];
5 int[] right = new int[N];
6 //填充初始值 使两个端点不会影响计算
7 Arrays.fill(left, Integer.MAX_VALUE);
8 Arrays.fill(right, Integer.MAX_VALUE);
9 //每个位置到左边人的距离
10 for (int i = 0; i < N; ++i) {
11 //该位置为1，无法坐人，距离人的距离置为0
12 if (seats[i] == 1) {
13 left[i] = 0;
14 } else if (i > 0) {
15 //该位置为0，那么离人的距离就是上一个位置离人的距离 + 1
16 left[i] = left[i-1] + 1;
17 }
18 }
19 //每个位置到右边的距离
20 for (int i = N-1; i >= 0; --i) {
21 //该位置为1，无法坐人，距离人的距离置为0
22 if (seats[i] == 1) {
23 right[i] = 0;
24 } else if (i < N-1) {
25 //该位置为0，那么离人的距离就是上一个位置离人的距离 + 1
26 right[i] = right[i+1] + 1;
27 }
28 }
29
30 int ans = 0;
31 for (int i = 0; i < N; ++i) {
32 //保留所有空位中离左右两边距离最大的值
33 if (seats[i] == 0) {
34 //每个位置离人的最近距离= 该位置离左右两边最近的那个值
35 ans = Math.max(ans, Math.min(left[i], right[i]));
36 }
37 }
38 return ans;
39}
时间复杂度：O(n)
空间复杂度：O(n)
方法二：数学法
思路：根据规律，如果两人之间有连续 K 个空座位，那么其中存在至少一个座位到两边最近的人的距离为 (K+1) / 2。而对于边缘的座位，它们的一侧没有人，那么认为它们到该侧最近的人的距离就是K。
代码如下：
1public static int maxDistToClosest(int[] seats) {
2 if (seats == null || seats.length < 2) {
3 return 0;
4 }
5 int firstK = 0;
6 int lastK = 0;
7 int midK = 0;
8 //第一个1还没出现
9 boolean first = false;
10 for (int seat : seats) {
11 if (seat == 0) {
12 if (!first) {
13 //第一个1还没出现，记录左端0的个数
14 firstK++;
15 } else {
16 //第一1已经出现，用lastK 记录中间的0的
17 lastK++;
18 }
19 } else {
20 if (!first) {
21 //第一个1出现
22 first = true;
23 } else {
24 //注意 用midK 记录中间的最长的0的个数
25 midK = Math.max(midK, lastK);
26 //lastK 重新归0，去记录下一个连续的0
27 lastK = 0;
28 }
29 }
30 }
31 //当一次遍历完数组后，我们已经知道左端的0的个数为firstK
32 //中间最长的0的个数为midK
33 //由于lastK碰见1就重新置为0
34 // 当lastK不为0，表明最后一个1到数组右边全是0，而lastK就是这些0的个数
35 //那么结果就是左右两端最大的那个，和中间的+1除于2进行比较，谁大就是结果
36 return Math.max((midK + 1) / 2, Math.max(lastK, firstK));
37}
时间复杂度：O(n)
空间复杂度：O(1)
以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 数组篇7_到最近的人的最大距离[难度：中等]