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

算法练习8——有序三元组中的最大值

LeetCode 100088 有序三元组中的最大值 I
LeetCode 100086 有序三元组中的最大值 II

给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < 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)

上面开的数组可以省略

贪心???
这应该是最优解了,思路如下:

  1. 目标是获取全局(nums[i] - nums[j]) * nums[k]最大值
  2. 转化问题,固定k,算出一个局部最大值序列[(nums[i] - nums[j]) * nums[0]], (nums[i] - nums[j]) * nums[1], ...,然后求序列中最大值
  3. 现在需要求nums[i] - nums[j]的最大值,当k=n时,假定nums[i] - nums[j]的最大值为a,此时a是由nums[:n]中的值计算出的,当k=n+1时,假定nums[i] - nums[j]的最大值为b,此时b是由nums[:n+1]中的值计算出的,可以发现,相邻两个nums[i] - nums[j]的最大值计算用的序列差一个最新的nums[n],此时有这么一个关系k=n时nums[i] - nums[j]的最大值自身max(nums[:n]) - nums[n]两者中的最大值
  4. 这样有如下代码
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)
# 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章:

算法练习8——有序三元组中的最大值

LeetCode 100088 有序三元组中的最大值 I LeetCode 100086 有序三元组中的最大值 II 给你一个下标从 0 开始的整数数组 nums 。 请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中&#xff0c;找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数&am…...

git创建

问: git remote add origin https://github.com//blog.git fatal: not a git repository (or any of the parent directories): .git 回答: 这个错误提示指出当前目录或其父目录中不存在.git文件夹&#xff0c;因此无法执行git相关操作。请确保你是在一个已经初始化为git仓库…...

yolov8 opencv模型部署(python版)

yolov8 opencv模型部署&#xff08;python版&#xff09; 使用opencv推理yolov8模型&#xff0c;以yolov8n为例子&#xff0c;一共几十行代码&#xff0c;没有废话&#xff0c;给出了注释&#xff0c;从今天起&#xff0c;少写一行代码&#xff0c;少掉一根头发。测试数据有需…...

Simulink仿真封装中的参数个对话框设置

目录 参数和对话框窗格 初始化窗格 文档窗格 为了更加直观和清晰的分析仿真&#xff0c;会将多个元件实现的一个功能封装在一起&#xff0c;通过参数对话框窗格&#xff0c;可以使用参数、显示和动作选项板中的对话框控制设计封装对话框。如图所示&#xff1a; 参数和对话框…...

【C++】class的设计与使用(十)重载iostream运算符

希望对某个类对象进行读写操作&#xff0c;直接cout<<类对象<<endl;或cin>>类对象;编译器会报错&#xff0c;所以我们必须提供一份重载的input/output运算符&#xff1a; 重载ostream运算符 ostream& operator<<(ostream &os, const Triangu…...

Java使用Scanner类实现用户输入与交互

概述&#xff1a; Scanner类是Java中的一个重要工具类&#xff0c;用于读取用户的输入。它提供了一系列的方法&#xff0c;可以方便地读取不同类型的数据&#xff0c;如整数、浮点数、字符串等。在本文中&#xff0c;我们将详细介绍Scanner类的使用方法&#xff0c;并通过两个…...

FFmpeg 命令:从入门到精通 | ffppeg 命令参数说明

FFmpeg 命令&#xff1a;从入门到精通 | ffmpeg 命令参数说明 FFmpeg 命令&#xff1a;从入门到精通 | ffmpeg 命令参数说明主要参数音频参数视频参数更多参考 FFmpeg 命令&#xff1a;从入门到精通 | ffmpeg 命令参数说明 本节主要介绍了 ffmpeg 命令的常用参数。 主要参数 …...

Chrome(谷歌浏览器)如何关闭搜索栏历史记录

目录 问题描述解决方法插件解决&#xff08;亲测有效&#xff09;自带设置解决步骤首先打开 地址 输入&#xff1a;chrome://flags关闭浏览器&#xff0c;重新打开Chrome 发现 已经正常 问题描述 Chrome是大家熟知的浏览器&#xff0c;但是搜索栏的历史记录如何自己一条条的删…...

基于Java的宠物医院管理系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...

使用WPS自动化转换办公文档: 将Word, PowerPoint和Excel文件转换为PDF

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

对pyside6中的textedit进行自定义,实现按回车可以触发事件。

我的实现方法是&#xff0c;先用qt designer写好界面&#xff0c;如下图&#xff1a; 接着将其生成的ui文件编译成为py文件。 找到里面这几行代码&#xff1a; self.textEdit QTextEdit(self.centralwidget)self.textEdit.setObjectName(u"textEdit")self.textEdit…...

Spark SQL

Spark SQL 一、Spark SQL概述二、准备Spark SQL的编程环境三、Spark SQL程序编程的入口四、DataFrame的创建五、DataFrame的编程风格六、DataSet的创建和使用七、Spark SQL的函数操作 一、Spark SQL概述 Spark SQL属于Spark计算框架的一部分&#xff0c;是专门负责结构化数据的…...

初识多线程

一、多任务 现实中太多这样同时做多件事的例子了&#xff0c;例如一边吃饭一遍刷视频&#xff0c;看起来是多个任务都在做&#xff0c;其实本质上我们的大脑在同一时间依旧只做了一件事情。 二、普通方法调用和多线程 普通方法调用只有主线程一条执行路径 多线程多条执行路径…...

Linux用户、用户组和文件权限的管理与实践

目录 一、Linux用户、用户组和文件权限的基础概念与作用1.1 Linux用户的概念与作用1.2 Linux用户组的概念与作用1.3 Linux文件权限的概念与作用 二、Linux用户、用户组和文件权限的具体操作实践2.1 创建新用户&#xff1a;从零开始构建用户体系2.2 修改用户和用户组属性&#x…...

【CMU15-445 Part-14】Query Planning Optimization I

Part14-Query Planning & Optimization I SQL is Declarative&#xff0c;只告诉想要什么而不需要说怎么做。 IBM System R是第一个实现query optimizer查询优化器的系统 Heuristics / Rules 条件触发 静态规则&#xff0c;重写query来remove 低效或者愚蠢的东西&#xf…...

七、垃圾收集中级

JVM由浅入深系列 JVM由浅入深系列一、关于Java性能的误解二、Java性能概述三、了解JVM概述四、探索JVM架构五、垃圾收集基础六、HotSpot中的垃圾收集七、垃圾收集中级八、垃圾收集高级👋垃圾收集中级 ⚽️1. 权衡收集器插件 就 Java 平台而言,有一点可能初学者未必能马上意…...

el-menu 导航栏学习(1)

最简单的导航栏学习跳转实例效果&#xff1a; &#xff08;1&#xff09;index.js路由配置&#xff1a; import Vue from vue import Router from vue-router import NavMenuDemo from /components/NavMenuDemo import test1 from /components/test1 import test2 from /c…...

Axios请求封装

安装axios&#xff0c;在net文件下新建index.js&#xff0c;封装InternalPsot请求&#xff1a; function internalPost(url,data,header,success,failure,errordefaultError()){axios.post(url,data,{headers:header}).then(({data})>{if (data.code200){success(data.dat…...

Pikachu靶场——XXE 漏洞

文章目录 1. XXE1.1 查看系统文件内容1.2 查看PHP源代码1.3 查看开放端口1.4 探测内网主机 1. XXE 漏洞描述 XXE&#xff08;XML External Entity&#xff09;攻击是一种利用XML解析器漏洞的攻击。在这种攻击中&#xff0c;攻击者通过在XML文件中插入恶意实体来触发解析器加载…...

vscode登录租的新服务器

1.connect to…… 选择 connect current window to host 2.configure SSH Host 选择本地配置文件 打开配置文件&#xff0c;把主机名端口号写进去 再返回vscode远程登录页面&#xff0c;左侧栏就会出现这个主机名了。...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...