948.令牌放置

令牌放置

你的初始能量为 power，初始分数为 0，只有一包令牌以整数数组 tokens 给出，其中每个 tokens[i] 是第 i 个令牌的值。

你的目标是通过有策略地使用这些令牌以最大化总分数。你可以根据以下规则进行操作：

• 如果你至少有 token[i] 点能量，你就可以播放第 i 个令牌。播放时，你将获得 1 分能量，但你需要消耗 token[i] 点能量。
• 如果你至少有 1 分，你可以选择播放第 i 个令牌。播放时，你将获得 token[i] 点能量，但你需要消费 1 分。

返回能得到的最大分数。

示例 1:

输入：tokens = [100], power = 50
输出：0

示例 2:

输入：tokens = [100,200,300,400], power = 200
输出：2

提示:

• 0 <= tokens.length <= 1000
• 0 <= power, tokens[i] <= 10^5

解析

使用贪心策略，将令牌排序，用双指针从两端遍历。能量足够时用最小令牌得分，能量不够时用最大令牌换能量。

var bagOfTokensScore = function (tokens, power) {
  tokens.sort((a, b) => a - b);
  let left = 0,
    right = tokens.length - 1;
  let score = 0,
    maxScore = 0;

  while (left <= right) {
    if (power >= tokens[left]) {
      power -= tokens[left];
      score++;
      left++;
      maxScore = Math.max(maxScore, score);
    } else if (score > 0) {
      power += tokens[right];
      score--;
      right--;
    } else {
      break;
    }
  }

  return maxScore;
};

时间复杂度 O(n log n)，空间复杂度 O(1)。