Formatted question description: https://leetcode.ca/all/1686.html

1686. Stone Game VI

Level

Medium

Description

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player’s turn, they can remove a stone from the pile and receive points based on the stone’s value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the i-th stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally.

Determine the result of the game, and:

  • If Alice wins, return 1.
  • If Bob wins, return -1.
  • If the game results in a draw, return 0.

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.

Constraints:

  • n == aliceValues.length == bobValues.length
  • 1 <= n <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100

Solution

Suppose there are two stones with indices 0 and 1. If Alice takes stone 0, then the difference between Alice and Bob is difference0 = aliceValues[0] - bobValues[1]. If Alice takes stone 1, then the difference between Alice and Bob is difference1 = aliceValues[1] - bobValues[0]. Therefore, difference0 - difference1 = (aliceValues[0] - bobValues[1]) - (aliceValues[1] - bobValues[0]) = (aliceValues[0] + bobValues[0]) - (aliceValues[1] + bobValues[1]). It can be seen that the optimal strategy for each player is to always take the stone that have the greatest total value for both players, where the total value of stone i is calculated as aliceValues[i] + bobValues[i].

Therefore, a greedy approach can be used. Use a priority queue to store the total values of the stones, where the maximum element is at the top of the priority queue. Each time poll one element from the priority queue and add the corresponding value to the current player’s total points. Finally, calculate the difference between Alice’s total points and Bob’s total points. If the difference is positive, return 1. If the difference is negative, return -1. If the difference is 0, return 0.

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                return array2[2] - array1[2];
            }
        });
        int length = aliceValues.length;
        for (int i = 0; i < length; i++)
            priorityQueue.offer(new int[]{aliceValues[i], bobValues[i], aliceValues[i] + bobValues[i]});
        int aliceScore = 0, bobScore = 0;
        for (int i = 0; i < length; i++) {
            int[] array = priorityQueue.poll();
            if (i % 2 == 0)
                aliceScore += array[0];
            else
                bobScore += array[1];
        }
        if (aliceScore > bobScore)
            return 1;
        else if (aliceScore < bobScore)
            return -1;
        else
            return 0;
    }
}

All Problems

All Solutions