C++刷leetcode（1423. 可获得的最大点数）【滑动窗口】

糖逗

题目描述：

1. 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
   
2. 
   
3. 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
   
4. 
   
5. 你的点数就是你拿到手中的所有卡牌的点数之和。
   
6. 
   
7. 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：cardPoints = [1,2,3,4,5,6,1], k = 3
    
14. 输出：12
    
15. 解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
    
16. 示例 2：
    
17. 
    
18. 输入：cardPoints = [2,2,2], k = 2
    
19. 输出：4
    
20. 解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
    
21. 示例 3：
    
22. 
    
23. 输入：cardPoints = [9,7,7,9,7,7,9], k = 7
    
24. 输出：55
    
25. 解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
    
26. 示例 4：
    
27. 
    
28. 输入：cardPoints = [1,1000,1], k = 1
    
29. 输出：1
    
30. 解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
    
31. 示例 5：
    
32. 
    
33. 输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
    
34. 输出：202
    
35.  
    
36. 
    
37. 提示：
    
38. 
    
39. 1 <= cardPoints.length <= 10^5
    
40. 1 <= cardPoints[i] <= 10^4
    
41. 1 <= k <= cardPoints.length
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int maxScore(vector<int>& cardPoints, int k) {
   
4.         //位置左边界（left）和右边界（right）满足：left + len - right - 1 = k的滑动窗口
   
5.         int len = cardPoints.size();
   
6.         int store = 0, total = 0;
   
7.         for(int i = 0; i < len; i++){
   
8.             if(i < len - k){
   
9.                 store += cardPoints[i];
   
10.             }
    
11.             total += cardPoints[i];
    
12.         }
    
13.         int res = total - store;
    
14.         for(int left = 1; left <= k; left++){
    
15.             store = store - cardPoints[left-1] + cardPoints[left + len - k - 1];
    
16.             res = max(total - store, res);
    
17.         }
    
18.         return res;
    
19.     }
    
20. };

复制代码

糖逗