【java】【leetcode】1423. 可获得的最大点数 滑窗

原题链接在此附上:1423. 可获得的最大点数
【java】【leetcode】1423. 可获得的最大点数 滑窗_第1张图片
这题有点意思,和我们平常做题思维不太一样,所谓滑窗,我觉得我们一般都会优先考虑划结果范围那个窗,但是这个题是反着来的,你要确定的结果是数组头部和尾部元素的最大和,并不适合我们直接进行滑窗操作,于是这道题的思路就变成了逆向操作,既然不能直接滑窗,就间接来,要求解头部和尾部元素的最大和,那是不是直接求整体的和然后减去数组中间元素最小和就是左右两端的最大和了?
所以我们写代码时要确定的几件事事情便是:

我们要划多大的窗?

已知我们要求前后k个数之和最大值
设:数组长度为 n ,窗口大小为size
那我们的滑窗大小即为,n-k(求解出n-k个数的最小和)。

那这个窗口要从哪开始划呢?

因为数组是无序的,我们没有办法去直接判断从哪边开始划,我们要确定出来一个区间,相加的值是最小的。

具体要怎么确定?

从头开始,前确定前 n-k 个数的和。
设我们滑窗区间之和为 sum ,首先计算出数组元素 0 下标到下标 n-k-1 的和。
此时设最小和为 minsum , minisum 默认值和 sum 相同。
我们现在只是确认了数组前 n-k 个数的和,无法保证这个和是最小的,所以我们要开始遍历进行判断。

怎么判断和筛选区间呢?

现在我们的窗口大小已经确定为 n-k 了,剩下的工作就是滑动窗口,确定窗口内加起来的数和最小。
所以我们要遍历数组剩下的位置,即 n-k 到 n 。
然后我们要做的就是:窗口向右移动的同时,窗口大小是固定的,有新的数字加入窗口中,那么我就要舍弃最左边的数字,这样才能保证我们的窗口大小不变。
然后确定新加进来的数与剔除掉最左部的数之后的和与最小和的关系。
如果它比较小,它将代替旧的最小和成为新的最小和。否则则继续遍历。
最终我们还差一步操作,我们求得是中间的最小和,不是题目要求的两端最大和。
所以我们需要 求解整个数组的元素之和,然后减去中间的最小和,即为最终结果。

    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length; // 确定数组长度
        int size = n - k; // 确定滑窗区间
        int sum = 0; // 滑窗区间总和
        for(int i =0; i 

你可能感兴趣的