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

The provided solution uses a greedy approach to solve the problem of capturing the maximum number of people in a game of hide and seek. The basic idea is to iterate over the array `team`, where '1' represents a seeker and '0' represents a hider. For each seeker found (i.e., when `team[i] == 1`), the algorithm tries to find the nearest hider within the distance `dist` (both before and after the seeker's position). The variable `left` is used to keep track of the position from where we start looking for a hider. The inner loop iterates from `left` to `i + dist` and checks if there is a hider within the valid distance range (`i - dist <= left <= i + dist`). If a hider is found, the counter `ans` is incremented, and the search for the next hider starts from the next position after the current `left`. This approach ensures that each hider is captured by the closest seeker, maximizing the number of captures.

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
        n = len(team) # Total number of people
        left = ans = 0  # Initialize pointers for the left boundary and answer
        for i, x in enumerate(team):  # Iterate over each person
            if x == 1:  # If the person is a seeker
                while left < n and left <= i + dist:  # Seek within the distance limit
                    if team[left] == 0 and i - dist <= left <= i + dist:  # Check if there's a hider in range
                        ans += 1  # Capture the hider
                        left += 1  # Move to the next potential hider
                        break
                    left += 1  # Move left pointer if no valid hider is found
        return ans  # Return the maximum number of captures