1423. Maximum Points You Can Obtain From Cards

Medium
Description

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

Example:

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

Intuition#

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

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

Approaches#

1: 前綴和枚舉#

  • 概念: 預計算左右前綴和，枚舉左邊取 0~k 張的所有組合。
  • 時間複雜度: O(k)
  • 空間複雜度: 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: 滑動視窗#

  • 概念: 找長度為 n-k 的子陣列最小和，答案 = 總和 - 最小窗口和。
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 反向思維 — 取兩端等於留中間，轉化為滑動視窗找最小
  • 關鍵技巧: 「從兩端取 k 個」的問題可轉化為「留中間 n-k 個」，用滑動視窗解決