1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        if (tokens.length == 0 || power < tokens[0])
            return 0;
        int score = 0, ans = 0;
        int left = 0, right = tokens.length - 1;
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score += 1;
                left += 1;
            } else {
                if (right != left) {
                    power += tokens[right];
                    score -= 1;
                    right -= 1;
                } else {
                    break;
                }
            }
        }
        return score;
    }
}

这道题这么想: 我们可以买token得points, 然后用一个point换一个token等价的power. 不同的token有不同的power. 那这样的话我们用power最便宜的token, 然后得到的points去换最大power的token来得到最多的power, 然后用更多的power买更多的token来换points.

于是我们想到使用sort. 一开始的power如果小于最小的tokens的power, 我们是一个point也得不到的, 直接返回0. 如果不是这样, 那我们的power够我们买若干个tokens, 假设为x个, 那x >= 1. 重复这个过程, 直到我们发现要么left > right, 此时直接得到了结果了; 要么是power不够了, 此时我们用point去到末尾的token换点儿power, 这个末尾token的power是大于等于我们目前买不起的token的, 于是换完后, 我们又可以去买若干个tokens了, 假设为y个, y >= 1. 重复这个过程, 直到left > right.

一个edge case需要注意, 在某个时刻, 我们买不起当前的token, 那么就要往后跑着去换, 如果此时left == right, 即使我们换好我们也没办法买了, 因为当前的token已经被用作换power了, 因此就不能买了. 这个case我们要额外考虑, 这也就是14行的功能.

时间复杂度: O(nlogn) sort需要用.
空间复杂度: O(logn) sort需要用.