Medium

题目描述

给你一个长度为 n 的二进制数组 possible。

Alice 和 Bob 正在玩一个由 n 个关卡组成的游戏。游戏中的一些关卡无法通过，而其他关卡总是可以通过。特别地，如果 possible[i] == 0，那么第 i 个关卡对于两个玩家来说都是无法通过的。玩家通过一个关卡可以获得 1 分，如果玩家未能通过关卡则失去 1 分。

在游戏开始时，Alice 将从第 0 个关卡开始按给定顺序玩一些关卡，之后 Bob 将玩剩下的关卡。

Alice 想要知道她应该至少玩多少个关卡才能获得比 Bob 更多的分数，如果两个玩家都以最优方式玩以最大化他们的分数。

返回 Alice 应该玩的最少关卡数以获得更多分数。如果这不可能，返回 -1。

注意每个玩家必须至少玩 1 个关卡。

示例 1：

输入：possible = [1,0,1,0]
输出：1
解释：
让我们看看 Alice 可以玩到的所有关卡：
- 如果 Alice 只玩关卡 0，Bob 玩其余关卡，Alice 有 1 分，而 Bob 有 -1 + 1 - 1 = -1 分。
- 如果 Alice 玩到关卡 1，Bob 玩其余关卡，Alice 有 1 - 1 = 0 分，而 Bob 有 1 - 1 = 0 分。
- 如果 Alice 玩到关卡 2，Bob 玩其余关卡，Alice 有 1 - 1 + 1 = 1 分，而 Bob 有 -1 分。

Alice 必须至少玩 1 个关卡才能获得更多分数。

示例 2：

输入：possible = [1,1,1,1,1]
输出：3

示例 3：

输入：possible = [0,0]
输出：-1

约束条件：

  • 2 <= n == possible.length <= 10^5
  • possible[i] 是 0 或 1

解题思路

这道题需要找到 Alice 玩的最少关卡数，使得她的分数严格大于 Bob 的分数。

核心思路： 根据题目提示，我们可以将数组中的 0 转换为 -1，这样每个元素就直接表示获得的分数（1 分或 -1 分）。然后问题转化为：找到最短的非空前缀，使得前缀和严格大于剩余部分的和。

算法步骤：

  1. 首先将 0 转换为 -1，计算整个数组的总和
  2. 使用前缀和的思想，遍历数组计算 Alice 的分数
  3. Bob 的分数 = 总和 - Alice 的分数
  4. 找到第一个使得 Alice 分数 > Bob 分数的位置
  5. 注意边界条件：Alice 不能玩所有关卡，Bob 也必须至少玩一个关卡

时间复杂度： O(n) - 只需要一次遍历 空间复杂度： O(1) - 只使用常数额外空间

推荐解法： 前缀和方法，简洁高效

代码实现

class Solution {
public:
    int minimumLevels(vector<int>& possible) {
        int n = possible.size();
        
        // 计算总分数（将0转换为-1）
        int totalScore = 0;
        for (int x : possible) {
            totalScore += (x == 1) ? 1 : -1;
        }
        
        // 遍历寻找最小的前缀长度
        int aliceScore = 0;
        for (int i = 0; i < n - 1; i++) {
            aliceScore += (possible[i] == 1) ? 1 : -1;
            int bobScore = totalScore - aliceScore;
            
            if (aliceScore > bobScore) {
                return i + 1;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumLevels(self, possible: List[int]) -> int:
        n = len(possible)
        
        # 计算总分数（将0转换为-1）
        total_score = sum(1 if x == 1 else -1 for x in possible)
        
        # 遍历寻找最小的前缀长度
        alice_score = 0
        for i in range(n - 1):
            alice_score += 1 if possible[i] == 1 else -1
            bob_score = total_score - alice_score
            
            if alice_score > bob_score:
                return i + 1
        
        return -1

public class Solution {
    public int MinimumLevels(int[] possible) {
        int n = possible.Length;
        
        // 计算总分数（将0转换为-1）
        int totalScore = 0;
        foreach (int x in possible) {
            totalScore += (x == 1) ? 1 : -1;
        }
        
        // 遍历寻找最小的前缀长度
        int aliceScore = 0;
        for (int i = 0; i < n - 1; i++) {
            aliceScore += (possible[i] == 1) ? 1 : -1;
            int bobScore = totalScore - aliceScore;
            
            if (aliceScore > bobScore) {
                return i + 1;
            }
        }
        
        return -1;
    }
}

var minimumLevels = function(possible) {
    const n = possible.length;
    const points = possible.map(x => x === 1 ? 1 : -1);
    
    let totalSum = points.reduce((sum, p) => sum + p, 0);
    let aliceSum = 0;
    
    for (let i = 0; i < n - 1; i++) {
        aliceSum += points[i];
        let bobSum = totalSum - aliceSum;
        
        if (aliceSum > bobSum) {
            return i + 1;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目