#1686

Stone Game VI

specialist · 710 · lc medium +30 · verified · 60.5% accepted · 894 likes · top 59%

Description

Alice and Bob take turns picking stones, Alice goes first. Each player picks the stone that best serves their interest — Alice maximizes the score difference and Bob minimizes it. The stones have separate values for each player given by aliceValues and bobValues. Return 1 if Alice wins, -1 if Bob wins, or 0 for a draw.

Example 1:

Input: aliceValues = [1,3], bobValues = [2,1]

Output: 1

Explanation:

If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.

Bob can only choose stone 0, and will only receive 2 points.

Alice wins.

Example 2:

Input: aliceValues = [1,2], bobValues = [3,1]

Output: 0

Explanation:

If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.

Draw.

Example 3:

Input: aliceValues = [2,4,3], bobValues = [1,6,7]

Output: -1

Explanation:

Regardless of how Alice plays, Bob will be able to have more points than Alice.

For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.

Bob wins.

Code

1

2

3

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int: