营销型网站建设便宜,网站建设与优化及覆盖率方案,连云港网站制作公司口碑好,欧洲十大服务器的推荐文章目录 前言LeetCode、2542. 最大子序列的分数【中等#xff0c;排序小顶堆】题目及类型思路及代码实现 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博客专家、Java领域优质创作者#xff0c;博客之星、阿里云平台优质作者、专注于Java后端技术领… 文章目录 前言LeetCode、2542. 最大子序列的分数【中等排序小顶堆】题目及类型思路及代码实现 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、2542. 最大子序列的分数【中等排序小顶堆】 来源《LeetCode 75》 题目及类型
题目链接2542. 最大子序列的分数
类型数据结构/树/小顶堆 思路及代码实现
思路排序小顶堆
对nums2进行降序排序排序数组中的值为nums2的索引位置值【目的快速定位k个元素中最小的值我们是直接由min中的最大值来开始推导】。从排序数组的第一个元素开始由于是顺序每次取到的i位置其nums2[i]都是在[i-k1,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个元素的小顶堆PriorityQueueInteger 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个值组成的sumlong 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—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取 整理者长路 整理时间2024.1.17
