LeetCode 1423. 可获得的最大点数

约 5 分钟
文章信息 10 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 华为 百度 携程 猿辅导
标签
数组 滑动窗口 前缀和

题目描述

✅ 1423. 可获得的最大点数

image-20260928234352461

image-20260928234352462

题意分析

每次只能从当前剩余牌的最左端或最右端拿一张，必须恰好拿走 k 张，求点数总和的最大值。拿牌顺序不影响最终点数，真正决定结果的是左边取多少张、右边取多少张。

解法：反向思考保留最小中间窗口

核心思路

[!blue]

从两端拿牌，最后拿走的一定是一段前缀和一段后缀，中间留下长度 remain = n - k 的连续区间。原数组总和 total 固定，所以取走的点数为 total - 保留区间的点数和，最大化取走就等价于最小化保留。

这个转换覆盖了全部合法取法：若从左边取 a 张，就从右边取 k - a 张，剩余区间从下标 a 开始、长度为 n - k；反过来，任意这个长度的窗口都可以通过取走它左边和右边的牌留下来。于是只需遍历所有长度为 remain 的窗口，找到最小窗口和。

相邻窗口只相差一张移入的牌和一张移出的牌，可以用 windowSum 滚动维护。右端移动到 right 时先加上 cardPoints[right]；若元素数量超过 remain，再减去 cardPoints[right - remain]，这样完整窗口始终是 [right - remain + 1, right]。

只有 right >= remain - 1 时窗口才凑够长度，此时才能更新 minWindow。若 k == n，没有需要保留的牌，直接返回总和，不进入滑窗流程。

解题步骤

  1. 遍历数组求 total，计算保留长度 remain = n - k。
  2. remain == 0 时直接返回 total。
  3. 从左到右移动 right，加上新牌，必要时减去窗口左侧多出的一张。
  4. 每当窗口长度达到 remain，用 windowSum 更新最小保留和 minWindow。
  5. 返回 total - minWindow。

Java 用整数最大值初始化 minWindow；Go 用 total 初始化也安全，因为题目中的点数都是正数，任何保留窗口的和都不会超过总和。

代码实现

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int total = 0;

        for (int point : cardPoints) {
            total += point;
        }

        int remain = cardPoints.length - k;

        // 全部取走时直接返回总和，避免继续扫描空的保留窗口。
        if (remain == 0) {
            return total;
        }

        int windowSum = 0;
        int minWindow = Integer.MAX_VALUE;

        for (int right = 0; right < cardPoints.length; right++) {
            windowSum += cardPoints[right];

            // 窗口元素超过 remain 个就吐出最左边那个，保持定长。
            if (right >= remain) {
                windowSum -= cardPoints[right - remain];
            }

            // 只有窗口凑满 remain 个元素后才是合法候选，否则半截窗口会污染最小值。
            if (right >= remain - 1) {
                minWindow = Math.min(minWindow, windowSum);
            }
        }

        return total - minWindow;
    }
}

func maxScore(cardPoints []int, k int) int {
    total := 0
    for _, point := range cardPoints {
        total += point
    }

    remain := len(cardPoints) - k
    // 全部取走时直接返回总和，避免继续扫描空的保留窗口。
    if remain == 0 {
        return total
    }

    windowSum := 0
    // remain < n 且点数恒为正，任意窗口和都严格小于 total，用它当初值是安全的。
    minWindow := total
    for right := 0; right < len(cardPoints); right++ {
        windowSum += cardPoints[right]
        // 窗口元素超过 remain 个就吐出最左边那个，保持定长。
        if right >= remain {
            windowSum -= cardPoints[right-remain]
        }

        // 只有窗口凑满 remain 个元素后才是合法候选，否则半截窗口会污染最小值。
        if right >= remain-1 && windowSum < minWindow {
            minWindow = windowSum
        }
    }

    return total - minWindow
}

复杂度分析

  • 时间复杂度：$O(n)$，求总和与滑窗各一次。
  • 空间复杂度：$O(1)$，只保存滚动状态。

关键点总结

[!green]

  • 两端取走的牌不一定连续，但留下的牌一定连续，适合转化成窗口问题。
  • 每个合法取法都对应一个长度为 n - k 的保留窗口，反过来也成立。
  • 总和固定，最大取走和等于总和减去最小保留和。
  • 相邻窗口只需一加一减，无需为每个窗口重新求和。

易错点总结

[!yellow]

  • 窗口未满就更新，会用短片段的较小和放大答案。
  • 窗口长度是 n - k，不是 k；要最小化的也是保留部分的和。
  • 新元素加入后，应移出下标 right - remain，才能留下恰好 remain 张牌。
  • 把最小和初值设为零，在正值输入下无法更新。
  • k == n 是合法情况，应直接返回总和，不能按普通非空窗口处理。

相似题目

题目 难度 关联与区别
643. 子数组最大平均数 I 简单 拿走两端k项等价于留下中间固定长度n-k的最小和窗口，可复用定长滑动和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/43421672
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！