【LeetCode】1423. 可获得的最大点数

痛定思痛。 2022-10-28 10:19 155阅读 0赞

# 1. 题目简介 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目分析 #

1.  题目的意思要求你`从数组的最左边或者最右边取出k个数字，取出的数字和最大`
2.  我们可以换个角度来思考：`当我们取出k个数字后，剩余的 len - k 个数字是不是一个连续的数组？如果我们求出连续数组的最小值，是不是相当于取出的数字和最大`
3.  所以，我们将这个问题转化为`给定一个数组，我们求在一段区间内的最小值`
4.  使用**滑动窗口**进行解决

# 3. 代码分析 #

class Solution {
        
        public int maxScore(int[] cardPoints, int k) {
        
        	// 获取cardPoints的长度
            int len = cardPoints.length;
            int sum = 0;
            // 求出cardPoints的总值
            for(int i = 0; i < len; i++){
        
                sum += cardPoints[i];
            }
            // 如果我们选取的卡牌数量大于我们的卡牌数量，则直接返回总值即可
            if(k >= len){
        
                return sum;
            }
            int sumSmall = 0;
            // 求出最原始的滑动窗口的值 [0,len-k)
            for(int i = 0; i < len - k; i++){
        
                sumSmall += cardPoints[i];
            }
    		
    		// 标记滑动窗口的大小
            int left = 0;
            int right = len - k;
            int min = sumSmall;
    			
    		// 每一次滑动都要加上右边的值，减去左边的值
            while(right < len){
        
                sumSmall += cardPoints[right++];
                sumSmall -= cardPoints[left++];
                min = Math.min(min, sumSmall);
            }
    		// 最后返回总值减去最小值即可
            return sum - min;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221024/8cace09a1d2b4e689920f34dbd9fe81c.png