948. Bag of Tokens - Medium

前往題目

想法

• 2 pointers，但怎麼利用這個規則是個問題

思路

貪婪

1. 排序，由小到大
2. 雙指針，分別指向兩端
3. 嘗試face up(因為可以增加score，也就是我們的最終目的，因此首選它)，不行的話face down(並且是選擇右指針，因為要最大化power，才能有本錢face down)，再不行直接回傳

Code

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        int res = 0, score = 0;

        // Sort, from small to large number
        Arrays.sort(tokens);

        // 2 pointers
        int l = 0, r = tokens.length - 1;

        while (l <= r) {
            // face up
            if (power >= tokens[l]) {
                power -= tokens[l]; // 減少power
                ++score;
                ++l; // 移動指針
                res = Math.max(res, score); // 更新最大值
            } else if (score >= 1) { // face down
                power += tokens[r]; // 增加power
                --score;
                --r;
                // 這裡不用更新，因為score被減去1，不可能更大
            } else { // can't play anymore
                break;
            }
        }

        return res;
    }
}