【ARTS】【LeetCode-2873】有序三元组中的最大值!
前言
仅做学习使用,侵删
什么是ARTS?
算法(Algorithm): 每周至少一道LeetCode算法题,加强编程训练和算法学习
阅读(Review): 阅读并点评至少一篇英文技术文章,提高英文水平
技巧 (Tip):学习至少一个技术技巧,总结、归纳日常工作中遇到的知识点
分享(Share):分析一篇有关点和思考的技术文章,建立影响力,输出价值观
算法(Algorithm)
2873.有序三元组中的最大值!
题目描述
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。示例 1:
输入:nums = [12,6,1,2,7]
输出:77
解释:下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。
示例 2:
输入:nums = [1,10,3,4,19]
输出:133
解释:下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。
示例 3:
输入:nums = [1,2,3]
输出:0
解释:唯一的下标三元组 (0, 1, 2) 的值是一个负数,(nums[0] - nums[1]) * nums[2] = -3 。因此,答案是 0 。提示:
• 3 <= nums.length <= 100
• 1 <= nums[i] <= 106
解题方法
方法一:暴力求解
思路
枚举所有满足 i<j<k 的三元组 (i,j,k),返回所有值大于等于 0 的三元组的最大值。
class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {res = Math.max(res, (long) (nums[i] - nums[j]) * nums[k]);}}}return res;}
}
复杂度分析
- 时间复杂度:O(n3),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
方法二:贪心
思路
固定三元组 (i,j,k) 的 j 和 k 时,由值公式 (nums[i]−nums[j])×nums[k] 可知,nums[i] 取区间 [0,j) 内的最大值时,(nums[i]−nums[j])×nums[k] 最大。使用两层循环分别枚举 k 和 j,同时使用 m 维护 [0,j) 的最大值,返回所有 (m−nums[j])×nums[k] 的最大值(若所有值都为负数,则返回 0)。
class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0;for (int k = 2; k < n; k++) {int m = nums[0];for (int j = 1; j < k; j++) {res = Math.max(res, (long)(m - nums[j]) * nums[k]);m = Math.max(m, nums[j]);}}return res;}
}
复杂度分析
- 时间复杂度:O(n2),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
方法三:贪心 + 前后缀数组
思路
令数组 nums 的长度为 n。根据值公式 (nums[i]−nums[j])×nums[k] 可知,当固定 j 时,nums[i] 和 nums[k] 分别取 [0,j) 和 [j+1,n) 的最大值时,三元组的值最大。我们使用 leftMax[j] 和 rightMax[j] 维护前缀 [0,j) 最大值和后缀 [j+1,n) 最大值,依次枚举 j,计算值 (leftMax[j]−nums[j])×rightMax[j],返回最大值(若所有值都为负数,则返回 0)。
public class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;int[] leftMax = new int[n];int[] rightMax = new int[n];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);}long res = 0;for (int j = 1; j < n - 1; j++) {res = Math.max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);}return res;}
}
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(n)。
方法四:贪心
思路
类似于方法三,我们固定 k,那么当 nums[i]−nums[j] 取最大值时,三元组的值最大。我们可以用 imax 维护 nums[i] 的最大值,dmax 维护 nums[i]−nums[j] 的最大值,在枚举 k 的过程中,更新 dmax 和 imax。
class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0, imax = 0, dmax = 0;for (int k = 0; k < n; k++) {res = Math.max(res, dmax * nums[k]);dmax = Math.max(dmax, imax - nums[k]);imax = Math.max(imax, nums[k]);}return res;}
}
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
分享(Share)
文章阅读
BeanUtils对比 12 种 Bean 自动映射工具,就它性能最拉跨_java beanutils modelmapper-CSDN博客
危险!请马上替换代码中的BeanUtils!!!
因为现在系统中正在使用BeanUtils 看到文章,但是经过询问基本不会出现这种问题
接口 TPS是什么
接口 TPS(Transactions Per Second)是指每秒钟系统能够处理的接口事务数量,它是衡量系统性能的重要指标之一。一个事务是指一个客户端向服务器发送请求,服务器进行处理并返回响应的完整过程。在接口性能测试中,TPS 常被用来评估接口的处理能力。TPS 值越高,说明系统在单位时间内能够处理更多的事务,性能越好
参考资料
作者:力扣官方题解
链接:2873. 有序三元组中的最大值 I - 力扣(LeetCode)
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。