849. 到最近的人的最大距离

难度: 中等

来源: 每日一题 2023.8.22

---

给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：seats = [0,1]
输出：1

提示：

• 2 <= seats.length <= 2 * 104
• seats[i] 为 0 或 1
• 至少有一个 空座位
• 至少有一个 座位上有人

class Solution {
    public int maxDistToClosest(int[] seats) {

    }
}

分析与题解

---

• 双指针 + 贪心

  这个问题其实就是模拟法+ 双指针 + 贪心, 我们只要分为以下几种情况.

  双指针 start 和 end 一开始都在等待区, 如图所示.

  

  int start = -1; 
  int end = -1;
  

  如果遍历过程中找到第一个 seats[i] = 1 , 那么 end 就变成 i, 这时候最佳的位置就是起始位置是离这个座位最远的位置.(情况1)

  

  经过上一次的计算, 我们继续重置 end = -1 进入等待区, 并使用 start 记录当前点. 然后继续遍历查找下一个不为0的点.

  

  当找到下一个点时, 那么我们需要从 start 和 end 之间找一个中点, 这个中点就是我们需要的点, 我们需要找到中点离 start 和 end 到底哪一个近就是我们需要的结果.(情况2)

  

  还有就是最后一种情况, 当我们找到了 start, 但是一直遍历到最后也没有找到另外一个 不为0 的点. 这时候最佳位置就是 结尾.(情况3)

  

  最终,整个解题过程如下所示.

  class Solution {
      public int maxDistToClosest(int[] seats) {
          int start = -1; int end = -1;
          int result = 0;
          // 一共有三种情况
          // start = -1; end = index; 这时候返回0
          // start = index1; end = index2; 这时候返回中点距离两个较小的距离
          // start = index; end = -1; 也是就是在寻找的时候 找到了起始点 ,没找到终点, 这时候返回 length - 1 - index;
          for(int i = 0; i < seats.length; i++) {
              int item = seats[i];
              // 只有 end 在移动时, 并且 item == 1 则停止判断
              // 这种case只能判断前两种情况
              if(end == -1 && item == 1) {
                  end = i;
                  if (start == -1) {
                      result = end;
                  } else {
                      result = Math.max(result, (end - start)/2);
                  }
                  // 移动start
                  start = end;
                  // 重置end
                  end = -1;
              }
  
              // 当 length -1 == i, end == -1 也是需要进行一次判断操作
              // 这种case补全了第三种情况
              if (i == seats.length - 1 && end == -1 && item == 0) {
                  result = Math.max(result,  seats.length - 1 - start);
              }
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

  结果如下所示.