948. 令牌放置

Medium

题目描述

你有一个初始能量值 power，初始分数为 0，以及一袋令牌，用整数数组 tokens 表示，其中 tokens[i] 表示第 i 个令牌的值。

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

正面朝上：如果你当前的能量至少为 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 (100)，将你的能量降至 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

解题思路

这是一个典型的贪心问题，需要合理安排令牌的使用策略。

核心思想

排序：首先对令牌数组进行排序，这样我们可以优先使用小值令牌获得分数，优先使用大值令牌补充能量。
双指针策略：
- 使用左指针指向最小值令牌（用于正面朝上获得分数）
- 使用右指针指向最大值令牌（用于正面朝下补充能量）
贪心策略：
- 获得分数时：优先使用值最小的令牌，这样消耗的能量最少
- 补充能量时：优先使用值最大的令牌，这样获得的能量最多

算法流程

对令牌数组进行升序排序
使用双指针 left 和 right 分别指向数组两端
在每轮循环中：
- 如果能量足够使用最小令牌，就正面朝上使用（获得分数）
- 如果能量不足但有分数且未使用的令牌数量大于1，就正面朝下使用最大令牌（补充能量）
- 否则跳出循环
记录过程中的最大分数值

这种策略确保我们总是以最少的能量获得分数，以最多的能量补充损失。

代码实现

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int left = 0, right = tokens.size() - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left++];
                score++;
                maxScore = max(maxScore, score);
            } else if (score > 0 && left < right) {
                power += tokens[right--];
                score--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
};

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        left, right = 0, len(tokens) - 1
        score = max_score = 0
        
        while left <= right:
            if power >= tokens[left]:
                power -= tokens[left]
                left += 1
                score += 1
                max_score = max(max_score, score)
            elif score > 0 and left < right:
                power += tokens[right]
                right -= 1
                score -= 1
            else:
                break
        
        return max_score

public class Solution {
    public int BagOfTokensScore(int[] tokens, int power) {
        Array.Sort(tokens);
        int left = 0, right = tokens.Length - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left++];
                score++;
                maxScore = Math.Max(maxScore, score);
            } else if (score > 0 && left < right) {
                power += tokens[right--];
                score--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

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++;
            maxScore = Math.max(maxScore, score);
        } else if (score > 0 && left < right) {
            power += tokens[right--];
            score--;
        } else {
            break;
        }
    }
    
    return maxScore;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n log n)
空间复杂度	O(1)

时间复杂度主要来自排序操作，双指针遍历只需要 O(n) 时间。空间复杂度为常数级别，只使用了有限的额外变量。

题目描述#

解题思路#

核心思想#

算法流程#

代码实现#

复杂度分析#