专门做折扣的网站,网页设计薪资多少,wordpress评论可看,通辽企业网站建设文章目录 题目原题链接思路#xff08;逆向思维#xff09; 题目 原题链接 Leetcode1423.可获得的最大点数 思路#xff08;逆向思维#xff09; 由题目可知#xff0c;从两侧选k张#xff0c;总数为n张#xff0c;即从中间选n - k张 nums总和固定#xff0c;要选k张最… 文章目录 题目原题链接思路逆向思维 题目 原题链接 Leetcode1423.可获得的最大点数 思路逆向思维 由题目可知从两侧选k张总数为n张即从中间选n - k张 nums总和固定要选k张最大的和即从中间选n - k张最小的和 综上原题 ----从 cardPoints中找长度为 n - k的连续段使其总和最小。 用sum代表nums的和用_min代表窗口中总和最小的值刚开始确定第一个窗口里面的值记为cur同时更新和最小_min窗口同时向后走进一个元素、出一个元素并更新_min最后返回sum - _min 代码
class Solution
{
public:int maxScore(vectorint cardPoints, int k) {int n cardPoints.size();int len n - k;//逆向思维转换窗口大小int sum 0, cur 0;//cur为当前窗口的总和for(auto e : cardPoints) sum e;//sum为cardPoints的总和for(int i 0; i len; i) cur cardPoints[i];//获取第一个窗口的值int _min cur;//窗口和最小的值for(int i len; i n; i){cur cardPoints[i] - cardPoints[i - len];_min min(_min, cur);}return sum - _min;}
};
