leetcode: 2789. 合并数组中的最大元素

这篇具有很好参考价值的文章主要介绍了leetcode: 2789. 合并数组中的最大元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次:

  • 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ,并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1:

输入: nums = [2, 3, 7, 9, 3]

输出: 21

解释: 我们可以在数组上执行下述操作:

- 选中 i = 0, 得到数组 nums = [5, 7, 9, 3].

- 选中 i = 1, 得到数组 nums = [5, 16, 3].

- 选中 i = 0, 得到数组 nums = [21, 3].

最终数组中的最大元素是21. 可以证明我们无法获得更大的元素.

示例 2:

输入: nums = [5, 3, 3]

输出: 11

解释: 我们可以在数组上执行下述操作:

- 选中 i = 1, 得到数组 nums = [5, 6].

- 选中 i = 0, 得到数组 nums = [11].

最终数组中只有一个元素, 即11.

题目的意思是数组中的元素可以吞噬前面一个不大于自身的元素,当所有元素都无法吞噬时,返回数组中可以获得的元素的最大值.要想获得保留元素的最大值,理应最后数组内剩余的元素应尽量的少, 也就是尽量让所有元素都被吞噬, 那我们就不能从前往后遍历进行吞噬了,因为这样会导致当前元素本来可以被吞噬,但是因为吞噬了前方元素使得自身又不能被吞噬了,这样中最终数组中的保留元素有可能变多,使得答案不正确,

例如nums = [1,1,1].

本来应该是下标2吞噬下标1,在吞噬下标0,这样得的结果是[3]

但如果下标1先吞噬下标0,那么nums = [2,1],导致最终的结果不正确.

所以我们应该从后向前遍历进行吞噬,这样可以保证吞噬的元素最多,使得保留元素最少,遍历过程中不断更新当前吞噬元素sum,如果遇到无法吞噬元素, 则更新ans的最大值,sum更新为0.

最终实现代码如下:

 1 class Solution {
 2     public long maxArrayValue(int[] nums) {
 3         long ans = -1, sum = 0;
 4         for (int i = nums.length - 1; i > -1 ; i--) {
 5             if (sum < nums[i]) {
 6                 ans = Math.max(ans, sum);
 7                 sum = 0;
 8             }
 9             sum += nums[i];
10         }
11         return Math.max(ans, sum);
12     }
13 }

 文章来源地址https://www.toymoban.com/news/detail-839780.html

到了这里,关于leetcode: 2789. 合并数组中的最大元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 图灵日记之Leetcode删除有序数组中的重复项&&合并两个有序数组&&移除链表元素

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月04日
    浏览(58)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(51)
  • 【LeetCode热题100】打卡第39天:数组中第K个最大元素&最大正方形

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月16日
    浏览(44)
  • 215. 数组中的第K个最大元素

    给定整数数组 nums 和整数 k ,请返回数组中第 **k** 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 示例 2: 提示: 1 = k = nums.length = 105 -104 = nums[i] = 104 解答

    2024年02月11日
    浏览(41)
  • 215数组中的第K个最大元素

    给定整数数组 nums 和整数 k ,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 示例 2: 提示: 1 = k = nums.length = 105 -104 = nums[i] = 104 在这个代

    2024年02月22日
    浏览(35)
  • 面试热题(数组中的第K个最大元素)

    给定整数数组  nums  和整数  k ,请返回数组中第  k  个最大的元素。 请注意,你需要找的是数组排序后的第  k  个最大的元素,而不是第  k  个不同的元素。        提到数组中最大元素,我们往往想到就是先给数组进行排序,然后取最大值,现在我们按照这个思路写一

    2024年02月13日
    浏览(53)
  • 【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

    题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1, 2, 4], l2 = [1, 3, 4] 输出:[1, 1, 2, 3, 4, 4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 我们的思路是,先定义

    2023年04月24日
    浏览(46)
  • Leetcode24-找到两个数组中的公共元素(2956)

    给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,它们分别含有 n 和 m 个元素。 请你计算以下两个数值: 统计 0 = i n 中的下标 i ,满足 nums1[i] 在 nums2 中 至少 出现了一次。 统计 0 = i m 中的下标 i ,满足 nums2[i] 在 nums1 中 至少 出现了一次。 请你返回一个长度为 2 的整数数组

    2024年01月20日
    浏览(43)
  • 算法训练day20Leetcode654最大二叉树617合并二叉树700二叉树中的1搜索98验证二叉搜索树

    https://leetcode.cn/problems/maximum-binary-tree/description/ 中序遍历递归,找到最大值然后作为根节点 凡是构造二叉树的题目都用前序遍历 (中左右) 为先构造中间节点,然后递归构造左子树和右子树。 确定递归函数的参数和返回值 参数传入的是存放元素的数组,返回该数组构造的二

    2024年01月21日
    浏览(41)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包