X

LEETCODE 1425. Constrained Subset Sum解题思路分析

题目大意:

带限制的子序列和

给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ,它们在原数组中的下标 i 和 j 满足 i < j 且 j – i <= k 。

数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。

示例 1:

输入:nums = [10,2,-10,5,20], k = 2
输出:37
解释:子序列为 [10, 2, 5, 20] 。

示例 2:

输入:nums = [-1,-2,-3], k = 1
输出:-1
解释:子序列必须是非空的,所以我们选择最大的数字。

示例 3:

输入:nums = [10,-2,-10,-5,20], k = 2
输出:23
解释:子序列为 [10, -2, -5, 20] 。

提示:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1425

解题思路分析:

本周的状态非常糟糕,周赛时,两道中等题在提交时共发生了3次提交错误,导致被罚30分钟,并且在连续提交错误之后,心态上也发生了一些变化,以至于在做最后一题时产生了一些厌烦情绪,这也是我今后需要改进的地方。

回到本题,这是本周周赛的压轴Hard级别题目,简单来说就是求一个数组中和最大的子序列。在不考虑子序列条件限制的情况下,和最大的一定是数组中所有正数组成的子序列。但是题目要求,子序列中相邻的两个元素在原数组中的下标差不能大于k,这就意味着我们要想得到符合条件最大子序列的话,那么该子序列中可能会掺入一些负数。

解题时,我们可以将原数组想象成为N个部分(子数组),其中每一个部分都是连续的正数(大于等于0),或者连续的负数。我们首先重点关注一下负数的部分,如果某一个负数子数组的长度小于等于k,那么我们可以将这一部分直接忽略掉。反之如果该负数子数组的长度大于k,那么,我们需要使用一个优先队列(PriorityQueue),从子数组首位开始向后循环,顺序向队列中添加这些负数,当队列的长度等于k时,我们从队列中取出一个最大值,将它作为子序列的一个对象,并将循环的下标设置为该对象所在下标,清空队列,继续重复上述操作,直到循环至子数组尾部为止。这样就能保证取出一些最大的负数(最小代价)来保证两个正数子数组相连通。

通过上述的操作,我们实际上可以得到类似以下这样的一个子序列:

[连续正数],(0或多个负数),[连续正数],(0或多个负数),[连续正数]....

上述序列实际上就是符合条件的一个子序列,但它并非是和最大的子序列,那么和最大的子序列一定是上述序列的某个子数组,因此问题就转化为在一个数组中找到和最大的子数组问题。这个问题的算法我们在之前的文章中多次提到过,简单来说,我们从第一位开始向后循环,利用一个sum对象来累加遍历过的所有数字和,并使用一个maxSum对象来记录最大sum,另外,如果当前数字加上sum之后反而比当前数字更小的话,那么不如舍弃之前的数字,将区间开始坐标设置为当前位置。这样遍历完整个数组,就能得到最大区间sum。也就是本题的解。

实现代码:

public int constrainedSubsetSum(int[] nums, int k) {
    // 存储连续负数的Queue
    PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->b[0]-a[0]);
    // 当前区间和
    int sum=0;
    // 最大区间和
    int masSum=Integer.MIN_VALUE;
    // 遍历每一个数字
    for(int i=0;i<nums.length;i++){
        // 如果当前数字大于等于0
        if(nums[i]>=0){
            // 将当前数字累加至sum
            sum+=nums[i];
            // 如果当前数字大于sum,舍弃之前的数字,将sum设为当前数字
            if(nums[i]>sum) sum=nums[i];
            // 更新最大区间和
            masSum=Math.max(sum, masSum);
            // 清理Queue
            q.clear();
        } else{ // 当前数字小于0
            // 将当前数字和下标加入Queue
            q.offer(new int[]{nums[i],i});
            // 如果Queue的大小等于k,
            // 说明我们需要在当前的连续k个数中选择一个数字,
            // 来确保子序列每两个相邻元素之间的下标小于等于k
            if(q.size()==k){
                // 取出Queue中最大的负数元素
                int[] item=q.poll();
                i=item[1]; // 将循环下标设置为当前元素下标
                sum+=item[0]; // 累加当前元素至sum
                // 如果当前数字大于sum,舍弃之前的数字,将sum设为当前数字
                if(item[0]>sum) sum=item[0];
                // 更新最大区间和
                masSum=Math.max(sum, masSum);
                q.clear(); // 清空Queue
            }
        }
    }
    return masSum;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 96.77% of Java online submissions for Constrained Subset Sum.

Memory Usage: 48.5 MB, less than 100.00% of Java online submissions for Constrained Subset Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1425-constrained-subset-sum解题思路分析/
Categories: leetcode
kwantong: