Leetcode

Stone Game VI

  • Time:O(n\log n)
  • Space:O(n)

C++

class Solution {
 public:
  int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
    const int n = aliceValues.size();
    vector<vector<int>> values;
    int a = 0;
    int b = 0;

    for (int i = 0; i < n; ++i)
      values.push_back({aliceValues[i], bobValues[i]});

    sort(begin(values), end(values), [](const auto& a, const auto& b) {
      return a[0] + a[1] > b[0] + b[1];
    });

    for (int i = 0; i < n; ++i)
      if (i % 2 == 0)
        a += values[i][0];
      else
        b += values[i][1];

    return a > b ? 1 : a < b ? -1 : 0;
  }
};

JAVA

class Solution {
  public int stoneGameVI(int[] aliceValues, int[] bobValues) {
    final int n = aliceValues.length;
    int[][] values = new int[n][];

    for (int i = 0; i < n; ++i)
      values[i] = new int[] {aliceValues[i], bobValues[i]};

    Arrays.sort(values, (a, b) -> b[0] + b[1] - a[0] - a[1]);

    int a = 0;
    int b = 0;

    for (int i = 0; i < n; ++i)
      if (i % 2 == 0)
        a += values[i][0];
      else
        b += values[i][1];

    return Integer.compare(a, b);
  }
}