当前位置: 首页 > news >正文

【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)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


http://www.mrgr.cn/news/97359.html

相关文章:

  • CSS快速上手
  • 手撕LLM(二):从源码出发,探索LoRA加载、推理全流程
  • CentOS Linux升级内核kernel方法
  • rust 同时处理多个异步任务,并在一个任务完成退出
  • 毕业设计:实现一个基于Python、Flask和OpenCV的人脸打卡Web系统(六)
  • Nginx 生产配置文件
  • 数据分析-Excel-学习笔记Day1
  • TYUTJava阶段测试
  • 新一代AI架构实践:数字大脑AI+智能调度MCP+领域执行APP的黄金金字塔体系
  • java发送http请求
  • k8s 1.23升级1.24
  • k8s之Ingress讲解
  • TDengine 从入门到精通(2万字长文)
  • 线程池/内存池/mysql连接池
  • 15分钟完成Odoo18.0安装与基本配置
  • Nginx 常见面试题
  • 现代Web表单验证的终极解决方案:构建可扩展的企业级验证系统
  • sentinel新手入门安装和限流,热点的使用
  • 003集——《利用 C# 与 AutoCAD API 开发 WPF 随机圆生成插件》(侧栏菜单+WPF窗体和控件+MVVM)
  • Gerapy二次开发:用户管理专栏页面样式与功能设计