令牌放置 图解题解

这道题到底在问什么

输入

tokens=[40,25,60,30,15,50], power=35

输出

2

最优解：一步一步想明白

1. 3记住这句「小的换分、大的换能量、能买就买买不动就卖」，下面每一帧都在套它。答案 ans 只升不随 score 回落，记的是历史峰值。
2. 4这是发到手的令牌，顺序是乱的。贪心策略要反复取「当前最小」和「当前最大」，乱序下没法一眼定位，所以第一步先排序。
3. 5排好序后，最左边的 15 是最便宜的令牌、买分优先选它；最右边的 60 是最值钱的、卖分优先选它。一头一尾正好对应两个指针。
4. 6左指针 i 指向最小令牌、负责买分，右指针 j 指向最大令牌、负责卖分。只要 i 不超过 j 就继续：先试着用 i 买，买不动再考虑用 j 卖。
5. 7先看左指针的最小令牌 15。当前能量 35 不小于它，说明买得起，那就贪心地用最便宜的把这一分先拿下。
6. 8正面朝上！花掉 15 点能量，能量从 35 降到 20，分数加到 1。这个令牌标绿，表示它被换成了分。
7. 9分数 1 创了新高，ans 刷新到 1。左指针右移，去看下一个最便宜的令牌还能不能接着买。
8. 10现在能量 20 连最小令牌 25 都买不起了。好在手里还有 1 分，可以反面朝下：盯住最值钱的 60，花 1 分把它换成一大笔能量。
9. 11反面朝下！花 1 分换来 60 点能量，能量从 20 升到 80，分数回落到 0。注意 ans 记的是历史峰值 1，卖分不会把它抹掉。右指针左移。
10. 12先看左指针的最小令牌 25。当前能量 80 不小于它，说明买得起，那就贪心地用最便宜的把这一分先拿下。
11. 13正面朝上！花掉 25 点能量，能量从 80 降到 55，分数加到 1。这个令牌标绿，表示它被换成了分。
12. 14分数 1 没超过历史最高 1，ans 保持不动。左指针右移，继续往下看。
13. 15先看左指针的最小令牌 30。当前能量 55 不小于它，说明买得起，那就贪心地用最便宜的把这一分先拿下。
14. 16正面朝上！花掉 30 点能量，能量从 55 降到 25，分数加到 2。这个令牌标绿，表示它被换成了分。
15. 17分数 2 创了新高，ans 刷新到 2。左指针右移，去看下一个最便宜的令牌还能不能接着买。
16. 18现在能量 25 连最小令牌 40 都买不起了。好在手里还有 2 分，可以反面朝下：盯住最值钱的 50，花 1 分把它换成一大笔能量。
17. 19反面朝下！花 1 分换来 50 点能量，能量从 25 升到 75，分数回落到 1。注意 ans 记的是历史峰值 2，卖分不会把它抹掉。右指针左移。
18. 20先看左指针的最小令牌 40。当前能量 75 不小于它，说明买得起，那就贪心地用最便宜的把这一分先拿下。
19. 21正面朝上！花掉 40 点能量，能量从 75 降到 35，分数加到 2。这个令牌标绿，表示它被换成了分。
20. 22分数 2 没超过历史最高 2，ans 保持不动。左指针右移，继续往下看。
21. 23左右指针交错，i 已经超过 j，可用的令牌都处理完了。绿色是买分用掉的、灰色是卖能量用掉的，过程到此为止。
22. 24回看整场：score 升到 2 时是最辉煌的一刻，后面虽然为换能量又卖回到 1，但 ans 早把这个峰值 2 记下了。所以最终答案就是 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        ans = score = 0
        i, j = 0, len(tokens) - 1
        while i <= j:
            if power >= tokens[i]:
                power -= tokens[i]
                score, i = score + 1, i + 1
                ans = max(ans, score)
            elif score:
                power += tokens[j]
                score, j = score - 1, j - 1
            else:
                break
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.size() - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.length - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = Math.max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问