发表于 2024.05.15

• 一般这种考虑左右两侧的数组题目(如845)，都可以通过两次遍历(从左，从右)+前缀和思路维护局部数据，然后再遍历一次数组以组成结果。在这个题目中，这个局部数据就是左侧/右侧连续为0的个数，最后再遍历数组，其中第i个座位距离最近有人座位的距离为min(左侧连续为0的个数, 右侧连续为0的个数)。需要注意左/右侧没人的情况。

  此外，这种双侧题目，可以使用双指针+贪心的方式以减少空间开销。使用left和right从左到右分别指向有人座位，其中right为left右侧的第一个有人座位(即left下一次会指向right)。因此，这两个有人座位的空隙中，最大的距离为(right - left) // 2。不断移动两个指针，直至right滑出数组即可。同样需要留意数组边缘左右侧没人的情况。

  使用前缀和思路：

  class Solution:
      def maxDistToClosest(self, seats: List[int]) -> int:
          # 统计左右两侧连续为0的次数
          left_dis = [-1] * len(seats)
          right_dis = [-1] * len(seats)
          for i in range(len(seats)):
              if seats[i] == 1:
                  left_dis[i] = 0
              else:
                  if i > 0 and left_dis[i - 1] != -1:
                      left_dis[i] = left_dis[i - 1] + 1
          for i in range(len(seats) - 1, -1, -1):
              if seats[i] == 1:
                  right_dis[i] = 0
              else:
                  if i + 1 < len(seats) and right_dis[i + 1] != -1:
                      right_dis[i] = right_dis[i + 1] + 1
          
          # 遍历数组，找到（左右两侧连续为0次数最小者）最大的元素
          ans = 0
          for i in range(len(seats)):
              dis = left_dis[i]
              # 注意边缘情况, left_dis[i] == -1会发生在左侧没人的情况, right_dis同理
              if dis == -1 or dis > right_dis[i] != -1:
                  dis = right_dis[i]
              ans = max(dis, ans)
          return ans

  使用双指针的思路：

  class Solution:
      def maxDistToClosest(self, seats: List[int]) -> int:
          left = -1
          right = 0
          # right先滑向第一个有人座位
          while right < len(seats) and seats[right] == 0:
              right += 1
  
          ans = right  # 初始化结果为right, 即坐在最左侧
  
          while right < len(seats):
              left, right = right, right + 1
              while right < len(seats) and seats[right] == 0:
                  right += 1
              # 如果right已经滑向了数组末尾, 此时坐在最右侧为该间隙内最远的距离
              max_dis = (right - left) // 2 if right != len(seats) else right - left - 1
              ans = max(ans, max_dis)
          return ans

• LC 题目链接