2024.3.14力扣每日一题——合并后数组中的最大元素

2024-04-05 20:52

本文主要是介绍2024.3.14力扣每日一题——合并后数组中的最大元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024.3.14

      • 题目来源
      • 我的题解
        • 方法一 贪心+倒序遍历

题目来源

力扣每日一题;题序:2789

我的题解

方法一 贪心+倒序遍历

个人思想:要想满足条件的基础上得到最大值,则需要贪心倒序遍历,从右往左只要满足条件就相加,不满足条件重新开始相加。感觉自己说不清楚,这里引用官方题解的说法。
官方说法:题目中的一次替换删除操作,其实是相当于将两个相邻并且非递减的数字进行求和合并。两个数字的和来替换掉原来的两个数字。而经过若干次这样的合并,整个数组的和是不变的。合并后数组中的每个元素,都是原数组的某个子数组的和,并且这些子数组拼接起来能构成整个原数组。为了使数组的最大值最大,可以贪心地做尽可能多的合并,直到整个数组都不能进行合并。合并的要求是后面的数字不小于前面的数字,就尽可能先合并靠后的数字,使其尽快能大,才能够合并前面的数字。
从后往前倒序遍历一次数组,依次比较两个相邻的元素,如果两个相邻的元素能够合并,就将其合并。如果不能合并,就继续往前判断。因为这样的操作流程,在比较过程中,靠后的数是所有操作流程可能性中能产生的最大值,而靠前的数,是所有操作流程可能性中能产生的最小值。如果在遍历过程中,比较的结果是不能合并,那么其他任何操作流程都无法合并这两个数。如果可以合并,那我们就贪心地合并,因为这样能使接下来的比较中,靠后的数字尽可能大。

时间复杂度:O(n)
空间复杂度:O(1)

public long maxArrayValue(int[] nums) {long res=nums[nums.length-1];for(int i=nums.length-2;i>=0;i--){res=nums[i]<=res?nums[i]+res:nums[i];}return res;
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

这篇关于2024.3.14力扣每日一题——合并后数组中的最大元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/878120

相关文章

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

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

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

利用Python实现Excel文件智能合并工具

《利用Python实现Excel文件智能合并工具》有时候,我们需要将多个Excel文件按照特定顺序合并成一个文件,这样可以更方便地进行后续的数据处理和分析,下面我们看看如何使用Python实现Exce... 目录运行结果为什么需要这个工具技术实现工具的核心功能代码解析使用示例工具优化与扩展有时候,我们需要将

Python实现获取带合并单元格的表格数据

《Python实现获取带合并单元格的表格数据》由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,所以本文我们就来聊聊如何使用Python实现获取带合并单元格的表格数据吧... 由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,现将将封装成类,并通过调用list_exc

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

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

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

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa