当前位置: 首页 > 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;左侧栏就会出现这个主机名了。...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...