LeetCode 1423. 可获得的最大点数

Categories:

题目描述
思路分析
1. 解法一：滑动窗口取最小补集（推荐）
相似题目

题目描述

✅ 1423. 可获得的最大点数

思路分析

解法一：滑动窗口取最小补集（推荐）

核心思路：

选取两端 k 张牌等价于丢弃中间连续的 n-k 张牌。

计算总和后，用滑动窗口求长度为 n-k 的最小子数组和。

最终答案为 total - minWindow。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int windowSize = n - k;
        int total = 0;
        for (int val : cardPoints) {
            total += val;
        }
        if (windowSize == 0) {
            return total;
        }

        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += cardPoints[i];
        }
        int minSum = windowSum;

        for (int i = windowSize; i < n; i++) {
            windowSum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = Math.min(minSum, windowSum);
        }

        return total - minSum;
    }
}

func maxScore(cardPoints []int, k int) int {
	n := len(cardPoints)
	windowSize := n - k

	total := 0
	for _, v := range cardPoints {
		total += v
	}
	if windowSize == 0 {
		return total
	}

	windowSum := 0
	for i := 0; i < windowSize; i++ {
		windowSum += cardPoints[i]
	}
	minSum := windowSum

	for i := windowSize; i < n; i++ {
		windowSum += cardPoints[i] - cardPoints[i-windowSize]
		if windowSum < minSum {
			minSum = windowSum
		}
	}

	return total - minSum
}

相似题目

题目	难度	考察点
1658. 将 x 减到 0 的最小操作数	中等	滑动窗口
209. 长度最小的子数组	中等	滑动窗口
643. 子数组最大平均数 I	简单	滑动窗口
1343. 大小为 K 且平均值大于等于阈值的子数组数目	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/43421672