关于网站设计的会议,外贸公司招聘条件,应用商店app下载安装最新版,最近国语视频在线观看免费播放LeetCode 100088 有序三元组中的最大值 I LeetCode 100086 有序三元组中的最大值 II 给你一个下标从 0 开始的整数数组 nums 。 请你从所有满足 i j k 的下标三元组 (i, j, k) 中#xff0c;找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数 j k 的下标三元组 (i, j, k) 中找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数则返回 0 。 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。 简单题我重拳出击中等题我唯唯诺诺
蛮力法
class Solution:def maximumTripletValue(self, nums: List[int]) - int:array [0] * len(nums)for i in range(2, len(nums)):for j in range(i):for k in range(j, i):array[i] max(array[i], (nums[j] - nums[k]) * nums[i])return max(array)
上面开的数组可以省略
贪心 这应该是最优解了思路如下
目标是获取全局(nums[i] - nums[j]) * nums[k]最大值转化问题固定k算出一个局部最大值序列[(nums[i] - nums[j]) * nums[0]], (nums[i] - nums[j]) * nums[1], ...然后求序列中最大值现在需要求nums[i] - nums[j]的最大值当kn时假定nums[i] - nums[j]的最大值为a此时a是由nums[:n]中的值计算出的当kn1时假定nums[i] - nums[j]的最大值为b此时b是由nums[:n1]中的值计算出的可以发现相邻两个nums[i] - nums[j]的最大值计算用的序列差一个最新的nums[n]此时有这么一个关系kn时nums[i] - nums[j]的最大值是自身和max(nums[:n]) - nums[n]两者中的最大值这样有如下代码
class Solution:def maximumTripletValue(self, nums: List[int]) - int:# 当前最大值curr_max 0# 当前最大的 nums[i] - nums[j]curr_v 0# 当前最大的 (nums[i] - nums[j]) * nums[k]ans 0n len(nums)for i in range(n):# 答案的最大值根据最大的 nums[i] - nums[j] 和当前数值的乘积更新ans max(ans, nums[i] * curr_v)# nums[i] - nums[j] 的最大值根据此前最大值减去当前数值更新curr_v max(curr_v, curr_max - nums[i])# 更新前缀最大值curr_max max(curr_max, nums[i])return ans# 作者小羊肖恩
# 链接https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/
# 来源力扣LeetCode
# 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
