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

2024-01-18 12:04

本文主要是介绍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个值组成的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;}
}

image-20240117195726842

资料获取

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

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

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

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


整理者:长路 整理时间:2024.1.17

这篇关于LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/618925

相关文章

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2