网站建设公司 成本结转,做那个网站的小编比较好,浙江平湖建设局网站,中国建设银行网站会员可以改名合并数组后的最大元素
难度#xff1a;中等
题目描述
给你一个下标从 0 开始、由正整数组成的数组 nums 。
你可以在数组上执行下述操作 任意 次#xff1a;
选中一个同时满足 0 i nums.length - 1 和 nums[i] nums[i 1] 的整数 i 。将元素 nums[i 1] …合并数组后的最大元素
难度中等
题目描述
给你一个下标从 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 。 解题思路 先捋一下题意输入一个数组然后对数组中的相邻元素进行合并计算合并后的结果替换掉原来的两个元素满足合并计算的要求1.相邻2.前面的元素小于等于后面的元素。一直执行这样的合并计算到整个数组没有满足合并计算要求的元素最后输出当前数组中最大的元素。 现在来解题还是贪心奥要想合并出最大的元素就要尽可能的多进行合并运算让后面的元素尽可能的大。通常我们都是正向遍历但是这次我们希望后面的元素越大越好那么我们这次选择的就是倒序遍历。
1. 逆向遍历数组
class Solution {public long maxArrayValue(int[] nums) {int temp nums.length - 1;int res nums[temp];for(int i temp - 1; i 0; i--){// 合并计算}return res;}
}
2. 合并计算
class Solution {public long maxArrayValue(int[] nums) {int temp nums.length - 1;long res nums[temp];for(int i temp - 1; i 0; i--){if(res nums[i]){res nums[i];}else{res nums[i];}}return res;}
} 这道题到这里呢也就解出来了个人感觉这道题倒是没有中等的难度不过力扣官方给中等难度应该是有他的原因的。 这道题难点在于去理解合并计算的过程我们可以把这个过程看成是大鱼吃小鱼的过程并且限制了只能向左去吃如果我们还是正向遍历的话就会导致前面的鱼比较大后面就没法吃出最大的鱼我们现在来模拟一下过程看看区别。
数组[1,2,4,5,6] 正向遍历[1,2,4,5,6]-[3,4,5,6]-[7,5,6]-[7,11] 输出结果11 逆向遍历[1,2,4,5,6]-[1,2,4,11]-[1,2,15]-[1,17]-[18] 输出结果18
这样大家应该就明白了。
代码分析
复杂度分析
时间复杂度O(n)。时间复杂度O(1)。 其中 n 是数组的长度。 代码优化
又到了代码优化环节代码优化可以是运行时间上的优化也可以是代码简洁度上的优化我们来尝试将代码写的更简洁。
class Solution {public long maxArrayValue(int[] nums) {long res nums[nums.length - 1];for(int i nums.length - 2; i 0; i--) res res nums[i] ? res nums[i] : nums[i];return res;}
}
