跟LintCode的算法题杠上了（1451到最近的人的最大距离）

本文主要是介绍跟LintCode的算法题杠上了（1451到最近的人的最大距离），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

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

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

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

样例 1:

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

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

思路

要考虑只有1个座位的情况，单独处理
2个座位之间相减的绝对值，除以2，然后向下取整，然后一次比较这个数的大小
要考虑座位不在头，或者不在尾的情况


public static void main(String[] args) {//int [] a = {0,1,0,0,0,1,0,0,0,0};int [] a = {0,0,0,0,0,1,0,0,0,0,0,0,0};int b = maxDistToClosest(a);System.out.println(b);
}public static int maxDistToClosest(int[] seats) {int seat = 0;//把座位的下标记录下来List<Integer> index = new ArrayList<>();for(int i = 0; i < seats.length; i ++){if(seats[i] == 1){index.add(i);}}if(index.size() == 1){//如果只有一个座位，那么就肯定是头或者尾巴才能保证最远距离int tou = index.get(0) - 0;int wei = seats.length - 1 - index.get(0);if(wei > tou){seat = wei;}else{seat = tou;}}else{int max = 0;//如果有多个座位的情况//找到座位里面下标距离最大的数，计算方式是相邻的2个数字取绝对值然后除以2 向下取整数for(int k = 0; k < (index.size() - 1); k ++){int seatIndex = (int)Math.floor(Math.abs(index.get(k) - index.get(k + 1)) / 2);if(seatIndex > max){max = seatIndex;}}//然后就要考虑第一个座位是不是在第0个位置，例如00001这种情况if(index.get(0) != 0){int seatIndex = index.get(0) - 0;if(seatIndex > max){max = seatIndex;}}//最后一个座位的下标是不是在最后一个位置，例如10000这样的if(index.get(index.size() - 1) < seats.length){int seatIndex = seats.length - 1 - index.get(index.size() - 1);if(seatIndex > max){max = seatIndex;}}seat = max;}return seat;
}