[LeetCode] 3096. Minimum Levels to Gain More Points

You are given a binary array possible of length n.

Alice and Bob are playing a game that consists of n levels. Some of the levels in the game are impossible to clear while others can always be cleared. In particular, if possible[i] == 0, then the ith level is impossible to clear for both the players. A player gains 1 point on clearing a level and loses 1 point if the player fails to clear it.

At the start of the game, Alice will play some levels in the given order starting from the 0th level, after which Bob will play for the rest of the levels.

Alice wants to know the minimum number of levels she should play to gain more points than Bob, if both players play optimally to maximize their points.

Return the minimum number of levels Alice should play to gain more points. If this is not possible, return -1.

Note that each player must play at least 1 level.

Example 1:
Input: possible = [1,0,1,0]
Output: 1

Explanation:
Let’s look at all the levels that Alice can play up to:

If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has -1 + 1 - 1 = -1 point.
If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 1 - 1 = 0 points, while Bob has 1 - 1 = 0 points.

If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 1 - 1 + 1 = 1 point, while Bob has -1 point.
Alice must play a minimum of 1 level to gain more points.

Example 2:
Input: possible = [1,1,1,1,1]
Output: 3

Explanation:
Let’s look at all the levels that Alice can play up to:

If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has 4 points.
If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 2 points, while Bob has 3 points.
If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 3 points, while Bob has 2 points.
If Alice plays till level 3 and Bob plays the rest of the levels, Alice has 4 points, while Bob has 1 point.
Alice must play a minimum of 3 levels to gain more points.

Example 3:
Input: possible = [0,0]
Output: -1

Explanation:
The only possible way is for both players to play 1 level each. Alice plays level 0 and loses 1 point. Bob plays level 1 and loses 1 point. As both players have equal points, Alice can’t gain more points than Bob.

Constraints:
2 <= n == possible.length <= 105
possible[i] is either 0 or 1.

得到更多分数的最少关卡数目。

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

Alice 和 Bob 正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。

游戏的一开始，Alice 将从第 0 级开始 按顺序 完成一些关卡，然后 Bob 会完成剩下的所有关卡。

假设两名玩家都采取最优策略，目的是 最大化 自己的得分，Alice 想知道自己 最少 需要完成多少个关卡，才能获得比 Bob 更多的分数。

请你返回 Alice 获得比 Bob 更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。

注意，每个玩家都至少需要完成 1 个关卡。

思路

思路是前缀和。Alice 需要确保自己在尽可能少完成关卡的情况下得分比 Bob 高，那么当 Alice 的得分第一次比 Bob 高的时候，我们就可以停下了，这个位置就是题目要求我们找的位置。

具体的做法是我们需要遍历 input 数组两遍。第一次遍历的时候统计整个数组的前缀和，记为 sum。第二次遍历的时候我们一边遍历，一边比较 Alice 和 Bob 的分数差。其中 Bob 在某个 index 的分数 = sum - Alice 在这个 index 停下的分数。注意第二次遍历的时候 for 循环要在 n - 1 停下，因为题目要求每个玩家都至少需要完成 1 个关卡。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int minimumLevels(int[] possible) {
        int n = possible.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int score = possible[i] == 1 ? 1 : -1;
            sum += score;
        }

        int alice = 0;
        for (int i = 0; i < n - 1; i++) {
            int score = possible[i] == 1 ? 1 : -1;
            alice += score;
            int bob = sum - alice;
            if (alice > bob) {
                return i + 1;
            }
        }
        return -1;
    }
}