Question

1989. 捉迷藏中可捕获的最大人数

English Version

题目描述

你正在和你的朋友玩捉迷藏游戏。在捉迷藏比赛中，人们被分成两组：是 “鬼” 的人，和不是 “鬼” 的人。是 “鬼” 的人想要抓住尽可能多的不是 “鬼” 的人。

给定一个 从 0 开始建立索引 的整数数组 team，其中只包含 0 (表示 不是 “鬼” 的人) 和 1 (表示是 “鬼” 的人)，以及一个整数 dist。索引 i 为 “鬼” 的人可以捕获索引在 [i - dist, i + dist](包括) 范围内且 不是 “鬼” 的任何一个人。

返回 _“鬼” 所能捕获的最大人数_。

 

示例 1:

输入: team = [0,1,0,1,0], dist = 3
输出: 2
解释:
在索引 1 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [1-3, 1+3] = [-2, 4] 内的人。
他们可以抓住索引 2 中不是 “鬼” 的人。
在索引 3 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [3-3, 3+3] = [0, 6] 内的人。
他们可以抓住索引 0 中不是 “鬼” 的人。
在索引 4 上不是 “鬼” 的人不会被抓住，因为在索引 1 和 3 上的人已经抓住了一个人。

示例 2:

输入: team = [1], dist = 1
输出: 0
解释:
没有 “鬼" 要抓的人。

示例 3:

输入: team = [0], dist = 1
输出: 0
解释:
没有 “鬼” 来抓人。

 

提示:

• 1 <= team.length <= 105
• 0 <= team[i] <= 1
• 1 <= dist <= team.length

解法

方法一：双指针

我们可以用两个指针 $i$ 和 $j$ 指向鬼和非鬼的人，初始时 $i=0$, $j=0$。

然后我们从左到右遍历数组，当遇到鬼时，即 $team[i]=1$ 时，如果此时 $j \lt n$ 并且 $team[j]=1$ 或者 $i - j \gt dist$，则指针 $j$ 循环右移，也即是说，我们要找到第一个不是鬼的人，且 $i$ 和 $j$ 之间的距离不超过 $dist$。如果找到了这样的人，则将指针 $j$ 右移一位，表示我们已经抓住了这个人，同时答案加一。继续遍历数组，直到遍历完整个数组。

最后返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

class Solution:
  def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
    ans = j = 0
    n = len(team)
    for i, x in enumerate(team):
      if x:
        while j < n and (team[j] or i - j > dist):
          j += 1
        if j < n and abs(i - j) <= dist:
          ans += 1
          j += 1
    return ans

class Solution {
  public int catchMaximumAmountofPeople(int[] team, int dist) {
    int ans = 0;
    int n = team.length;
    for (int i = 0, j = 0; i < n; ++i) {
      if (team[i] == 1) {
        while (j < n && (team[j] == 1 || i - j > dist)) {
          ++j;
        }
        if (j < n && Math.abs(i - j) <= dist) {
          ++ans;
          ++j;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int catchMaximumAmountofPeople(vector<int>& team, int dist) {
    int ans = 0;
    int n = team.size();
    for (int i = 0, j = 0; i < n; ++i) {
      if (team[i]) {
        while (j < n && (team[j] || i - j > dist)) {
          ++j;
        }
        if (j < n && abs(i - j) <= dist) {
          ++ans;
          ++j;
        }
      }
    }
    return ans;
  }
};

func catchMaximumAmountofPeople(team []int, dist int) (ans int) {
  n := len(team)
  for i, j := 0, 0; i < n; i++ {
    if team[i] == 1 {
      for j < n && (team[j] == 1 || i-j > dist) {
        j++
      }
      if j < n && abs(i-j) <= dist {
        ans++
        j++
      }
    }
  }
  return
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}