1423. Maximum Points You Can Obtain From Cards

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1423Maximum Points You Can Obtain From CardsGreedyMediumGreedy

給定一個整數陣列 cardPoints 和整數 k。每次只能從陣列的最左或最右邊取一張卡牌，共取 k 張。回傳能獲得的最大點數。

Example:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3 Output: 12

Intuition

TIP

取左右共 k 張 = 總和減去中間連續 n-k 張的最小和。

從左邊取 i 張、右邊取 k-i 張，等價於留下中間 n-k 張連續子陣列
問題轉化為：找長度為 n-k 的子陣列使其和最小
用滑動視窗找最小和

Approaches

1. Prefix Sum Enumeration — O(k) / O(k)

Idea: 預計算左右前綴和，枚舉左邊取 0~k 張的所有組合。
Time: O(k)
Space: O(k)

class Solution {
    fun maxScore(cardPoints: IntArray, k: Int): Int {
        val n = cardPoints.size
        val leftSum = IntArray(k + 1)
        for (i in 0 until k) leftSum[i + 1] = leftSum[i] + cardPoints[i]

        var result = 0
        var rightSum = 0
        for (i in 0..k) {
            // 左邊取 k-i 張，右邊取 i 張
            result = maxOf(result, leftSum[k - i] + rightSum)
            if (i < k) rightSum += cardPoints[n - 1 - i]
        }
        return result
    }
}

⭐ 2. Sliding Window — O(n) / O(1)

Idea: 找長度為 n-k 的子陣列最小和，答案 = 總和 - 最小窗口和。
Time: O(n)
Space: O(1)

class Solution {
    fun maxScore(cardPoints: IntArray, k: Int): Int {
        val n = cardPoints.size
        val windowSize = n - k
        val totalSum = cardPoints.sum()

        var windowSum = 0
        for (i in 0 until windowSize) windowSum += cardPoints[i]

        var minWindowSum = windowSum
        for (i in windowSize until n) {
            windowSum += cardPoints[i] - cardPoints[i - windowSize]
            minWindowSum = minOf(minWindowSum, windowSum)
        }
        return totalSum - minWindowSum
    }
}

🔑 Takeaways

Pattern: 反向思維 — 取兩端等於留中間，轉化為滑動視窗找最小
Key trick: 「從兩端取 k 個」的問題可轉化為「留中間 n-k 個」，用滑動視窗解決

Intuition

Approaches

🔑 Takeaways

相關題目