0948. 令牌放置【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 双指针

1. 📝 题目描述

• leetcode

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

你的目标是通过有策略地使用这些令牌以 最大化 总 分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：

• 朝上：如果你当前 至少 有 tokens[i] 点 能量，可以使用令牌 i，失去 tokens[i] 点 能量，并得到 1 分。
• 朝下：如果你当前至少有 1 分，可以使用令牌 i，获得 tokens[i] 点 能量，并失去 1 分。

在使用 任意 数量的令牌后，返回我们可以得到的最大 分数。

---

示例 1：

输入：tokens = [100], power = 50
输出：0
解释：因为你的初始分数为 0，无法使令牌朝下。你也不能使令牌朝上因为你的能量（50）比 tokens[0] 少（100）。

示例 2：

输入：tokens = [200,100], power = 150
输出：1
解释：使令牌 1 正面朝上，能量变为 50，分数变为 1。
不必使用令牌 0，因为你无法使用它来提高分数。可得到的最大分数是 1。

示例 3：

输入：tokens = [100,200,300,400], power = 200
输出：2
解释：按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 (100)正面朝上，能量变为 100，分数变为 1
2. 令牌 3 (400)正面朝下，能量变为 500，分数变为 0
3. 令牌 1 (200)正面朝上，能量变为 300，分数变为 1
4. 令牌 2 (300)正面朝上，能量变为 0，分数变为 2

可得的最大分数是 2。

---

提示：

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

2. 🎯 s.1 - 排序 + 双指针

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} tokens
 * @param {number} power
 * @return {number}
 */
var bagOfTokensScore = function (tokens, power) {
  tokens.sort((a, b) => a - b)
  let lo = 0,
    hi = tokens.length - 1
  let score = 0,
    maxScore = 0

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

  return maxScore
}

• 时间复杂度：$O(n\log n)$，排序为主要开销
• 空间复杂度：$O(1)$，原地排序

算法思路：

• 排序后，用最小的令牌换分数（正面朝上），用最大的令牌换能量（正面朝下）
• 左指针从最小端开始，右指针从最大端开始
• 优先用小面值令牌得分，能量不足且有分数时用大面值令牌换能量