LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

这篇具有很好参考价值的文章主要介绍了LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引:博客目录索引(持续更新)

视频平台:b站-Coder长路


LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

来源:《LeetCode 75》

题目及类型

题目链接:2542. 最大子序列的分数

类型:数据结构/树/小顶堆


思路及代码实现

思路:排序+小顶堆

  1. 对nums2进行降序排序(排序数组中的值为nums2的索引位置值)【目的:快速定位k个元素中最小的值,我们是直接由min中的最大值来开始推导】。
  2. 从排序数组的第一个元素开始,由于是顺序,每次取到的i位置,其nums2[i]都是在[i-k+1,i]中最小的,那么就可以实际就是题目中的min(nums2[i0] , nums2[i1], … ,nums2[ik - 1])。那么对于进行k个元素的和怎么计算呢?每次取到索引值,我们就直接累加这个nums1[i]到sum中,并且将这个值添加到一个小顶堆里。
  3. 每次得到一个新的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;
    }
}

LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】,# LeetCode,leetcode,算法,职场和发展

资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 整理时间:2024.1.17文章来源地址https://www.toymoban.com/news/detail-800637.html

到了这里,关于LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 软考知识点——数据结构:大顶堆与小顶堆、哈夫曼树

    目录 一、大顶堆与小顶堆 1.大顶堆与小顶堆的概念 2.大顶堆的构建 二、哈夫曼树 1.哈夫曼树的定义 2.基本概念 3.构造哈夫曼树 4.哈夫曼编码 大顶堆:每个结点的值都大于或等于其左右孩子结点的值。 小顶堆:每个结点的值都小于或等于其左右孩子结点的值。 以数组A=(2,

    2024年02月06日
    浏览(39)
  • 【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大

    双指针 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 贪心算法 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对数组执行 至多 k 次操作: 从数组中选择一个下标 i ,将 nums[i] 增加 或者 减少 1 。 最终数组的频率分数定义为数组

    2024年02月04日
    浏览(63)
  • 【LeetCode-中等】221. 最大正方形(详解)

    在一个由  \\\'0\\\'  和  \\\'1\\\'  组成的二维矩阵内,找到只包含  \\\'1\\\'  的最大正方形,并返回其面积。 力扣原题链接   暴力法一般不是最优解,但是可以拿来练手 由于正方形的面积等于边长的平方,因此要找到最大正方形的面积,首先需要找到最大正方形的边长,然后计算最大边

    2024年02月13日
    浏览(48)
  • [leetcode] 2530. 执行 K 次操作后的最大分数 M

    给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。 在一步 操作 中: 选出一个满足 0 = i nums.length 的下标 i , 将你的 分数 增加 nums[i] ,并且 将 nums[i] 替换为 ceil(nums[i] / 3) 。 返回在 恰好 执行 k 次操作后,你可能获得的最大分数。 向上取整函数 c

    2024年02月07日
    浏览(43)
  • LeetCode、162. 寻找峰值【中等,最大值、二分】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月20日
    浏览(46)
  • 【Leetcode】【每日一题】【中等】1465. 切割后面积最大的蛋糕

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。 https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/?envType=daily-questionenvId=2023-10-27 矩形

    2024年02月07日
    浏览(33)
  • LeetCode_动态规划_中等_918.环形子数组的最大和

    给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空子数组的最大可能和。 环形数组意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。 子数组最多只能包含固定缓冲区 nums 中的每个元素

    2024年02月09日
    浏览(42)
  • 【LeetCode-中等题】148. 排序链表

    把链表放到List集合,排好序,再依据List集合创建一个新有序链表返回就行了 优先队列 往这个优先队列中插入元素时,会按照节点 val 属性的大小顺序进行排序,即小的节点排在前面,大的节点排在后面。依次谈栈再创建新链表 优先队列声明 先找到中间点 按中间点切割链表

    2024年02月11日
    浏览(40)
  • 每天一道leetcode:516. 最长回文子序列(动态规划&中等)

    给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 1 = s.length = 1000 s 仅由小写英文字母组成 动态规划 ,使用二维dp数组记录[i,j]间的最大回文子序列长度

    2024年02月13日
    浏览(45)
  • 【LeetCode-中等】剑指 Offer 31. 栈的压入、弹出序列(详解)

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例

    2024年02月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包