前言
博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引:博客目录索引(持续更新)
视频平台:b站-Coder长路
LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】
来源:《LeetCode 75》
题目及类型
题目链接:2542. 最大子序列的分数
类型:数据结构/树/小顶堆
思路及代码实现
思路:排序+小顶堆
- 对nums2进行降序排序(排序数组中的值为nums2的索引位置值)【目的:快速定位k个元素中最小的值,我们是直接由min中的最大值来开始推导】。
- 从排序数组的第一个元素开始,由于是顺序,每次取到的i位置,其nums2[i]都是在[i-k+1,i]中最小的,那么就可以实际就是题目中的min(nums2[i0] , nums2[i1], … ,nums2[ik - 1])。那么对于进行k个元素的和怎么计算呢?每次取到索引值,我们就直接累加这个nums1[i]到sum中,并且将这个值添加到一个小顶堆里。
- 每次得到一个新的i位置时,sum会累加nums1[i],同时将nums2[i]作为min(k个nums2元素)的最小值,最后计算得到结果后,再将小顶堆中的最小值移除(问这个移除是否影响到min最小值的确定,并不会原因是每次取到的nums2[i]都已经是前面范围的最小值了!所以我们也无需管移除的最小值是什么)
复杂度分析:时间复杂度O(n.logn);空间复杂度O(n)
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
//维护k个元素的小顶堆
PriorityQueue<Integer> queue = new PriorityQueue<>(k);
//创建nums2数组的索引数组,并且根据nums2数组中的值降序排列的索引数组
Integer[] sorteds = new Integer[n];
for (int i = 0; i < n; i ++) {
sorteds[i] = i;
}
//根据nums2的值进行降序排列
Arrays.sort(sorteds, (i, j)->nums2[j]-nums2[i]);
//定义一个k个值组成的sum
long sum = 0L;
//首先合并k-1个元素值
for (int i = 0; i < k - 1; i ++) {
sum += nums1[sorteds[i]];//合并的是基于索引值的nums1数组元素
queue.offer(nums1[sorteds[i]]);
}
long ans = 0L;
//遍历剩余的所有元素,每次构成一个新的组合
for (int i = k - 1; i < n; i ++) {
//将当前值累加,并将当前值添加到
sum += nums1[sorteds[i]];
queue.offer(nums1[sorteds[i]]);
//sum即为k个元素之和 nums2[sorteds[i]]则为k个中最小的值
ans = Math.max(ans, sum * nums2[sorteds[i]]);
//出小顶堆中最小的元素
sum -= queue.poll();
}
return ans;
}
}
资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅:在下方专栏👇🏻
- 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
- 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
- 学习与生活-专栏:可以了解博主的学习历程
- 算法专栏:算法收录
更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅文章来源:https://www.toymoban.com/news/detail-800637.html
整理者:长路 整理时间:2024.1.17文章来源地址https://www.toymoban.com/news/detail-800637.html
到了这里,关于LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!