LC.P1423[可获得的最大点数]

方法一：滑动窗口逆向思维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    // 求 k 张点数的最大和，等价于求 n - k 张连续的牌的最小和
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, m = n - k, sum = 0;
        for (int i = 0; i < m; ++i) sum += cardPoints[i];
        int total = sum, minSum = sum;
        for (int i = m; i < n; ++i) {
            total += cardPoints[i];
            sum += cardPoints[i] - cardPoints[i - m];
            minSum = Math.min(minSum, sum);
        }
        return total - minSum;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

方法二：滑动窗口正向思维

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for (int i = 0; i < k; ++i) sum += cardPoints[i];
        int ans = sum;
        for (int i = 1; i <= k; ++i) {
            sum += cardPoints[n - i] - cardPoints[k - i];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
  • 时间复杂度：$O(k)$
  • 空间复杂度：$O(1)$