【每日一题】元素和最小的山形三元组 I

文章目录

  • Tag
  • 题目来源
  • 解题思路
    • 方法一:预处理+枚举
  • 写在最后

Tag

【预处理+枚举】【数组】【2024-03-29】


题目来源

2908. 元素和最小的山形三元组 I


解题思路

方法一:预处理+枚举

思路

朴素的方法是枚举所有可能的 山形三元组,找出最小的元素和。该方法的时间复杂度为 O ( n 3 ) O(n^3) O(n3),对于本题的数据规模完全可以通过。

但是有最优的解法,对数组进行预处理,维护两个数组 leftMinrightMinleftMin[i] 表示位置 i 处及其左侧最小的元素值,rightMin[i] 表示位置 i 处及其右侧最小的元素值。

最后枚举 山形三元组 的中间位置元素,找出符合要求的最小元素和。

具体实现见代码。

实现代码

class Solution {
public:int minimumSum(vector<int>& nums) {int n = nums.size();vector<int> leftMin(n), rightMin(n);leftMin[0] = nums[0];for (int i = 1; i < n; ++i) {leftMin[i] = min(leftMin[i-1], nums[i]);}rightMin[n-1] = nums[n-1];for (int i = n-2; i >= 0; --i) {rightMin[i] = min(rightMin[i+1], nums[i]);}int res = 300;for (int i = 1; i < n-1; ++i) {if (nums[i] > leftMin[i-1] && nums[i] > rightMin[i+1])res = min(res, nums[i] + leftMin[i-1] + rightMin[i+1]);}return res == 300 ? -1 : res;}
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为数组 nums 的长度。

空间复杂度: O ( n ) O(n) O(n)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/290260.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

荟萃分析R Meta-Analyses 3 Effect Sizes

总结 效应量是荟萃分析的基石。为了进行荟萃分析&#xff0c;我们至少需要估计效应大小及其标准误差。 效应大小的标准误差代表研究对效应估计的精确程度。荟萃分析以更高的精度和更高的权重给出效应量&#xff0c;因为它们可以更好地估计真实效应。 我们可以在荟萃分析中使用…

新手体验OceanBase社区版V4.2:离线部署单节点集群

本文源自OceanBase用户的分享 先简单总结如下&#xff1a; 1.本文适合初学者体验OceanBase社区版 v4.2.2 2.仅需准备一台配置为2C/8G的Linux虚拟机 3.通过离线方式安装&#xff0c;以便更直观地了解安装过程 一、Linux系统准备 在宿主机(即你的windows PC电脑)上安装vbox软…

酷柚易讯无人空间美团对接说明文档

美团对接后可在预约小程序上进行团购券核销 1、美团对接采用美团北极星开放平台&#xff0c;用户需注册开放平台https://open.dianping.com/ 2、创建应用&#xff0c;选择工具型&#xff0c;提交相关资料 3、创建应用后需要开通对应的团购核销权限 4、获取对应key与密钥填写至…

如何为企业策划一场XR虚拟直播?

活动年年办&#xff0c;都是老一套&#xff0c;想玩点新花样&#xff1f; 预算有限&#xff0c;但还是想把活动办的逼格高一点&#xff1f; 想通过活动&#xff0c;让更多的人知道自己企业的品牌&#xff1f; 随着AIGC技术的不断演变&#xff0c;企业活动的形式和内容也在不…

windows 下用使用api OCI_ConnectionCreate连接oracle报错 TNS:无法解析指定的连接标识符

背景&#xff0c;两台服务器系统一样&#xff0c;oracle版本一样&#xff0c;其中一台服务器在运行程序的时候报错 TNS:无法解析指定的连接标识符 但是PL/SQL可以正常连接&#xff0c;怀疑是oracle配置文件的原因 tnsnames.ora配置文件大概作用&#xff1a;是Oracle客户端的网…

前后端分离开发【Yapi平台】【Swagger注解自动生成接口文档平台】

前后端分离开发 介绍开发流程Yapi&#xff08;api接口文档编写平台&#xff09;介绍 Swagger使用方式1). 导入knife4j的maven坐标2). 导入knife4j相关配置类3). 设置静态资源映射4). 在LoginCheckFilter中设置不需要处理的请求路径 查看接口文档常用注解注解介绍 当前项目中&am…

腾讯云4核8G服务器多少钱?12M带宽646元15个月,买1年送3月

2024年腾讯云4核8G服务器租用优惠价格&#xff1a;轻量应用服务器4核8G12M带宽646元15个月&#xff0c;CVM云服务器S5实例优惠价格1437.24元买一年送3个月&#xff0c;腾讯云4核8G服务器活动页面 txybk.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云4核8G服务器优惠价格 轻…

springcloud微服务项目,通过gateway+nacos实现灰度发布(系统不停机升级)

一、背景 灰度发布的目的是保证系统的高可用&#xff0c;不停机&#xff0c;提升用户体验。在微服务系统中&#xff0c;原有系统不下线&#xff0c;新版系统与原有系统同时在线&#xff0c;通过访问权重在线实时配置&#xff0c;可以让少量用户先应用新版本功能&#xff0c;如…

机器学习:数据降维主成分分析PCA

一、引言 1.数据分析的重要性   在当今的信息爆炸时代&#xff0c;数据已经渗透到各个行业和领域的每一个角落&#xff0c;成为决策制定、科学研究以及业务发展的重要依据。数据分析则是从这些数据中提取有用信息、发现潜在规律的关键手段。通过数据分析&#xff0c;我们能够…

【学习笔记】java项目—苍穹外卖day01

文章目录 苍穹外卖-day01课程内容1. 软件开发整体介绍1.1 软件开发流程1.2 角色分工1.3 软件环境 2. 苍穹外卖项目介绍2.1 项目介绍2.2 产品原型2.3 技术选型 3. 开发环境搭建3.1 前端环境搭建3.2 后端环境搭建3.2.1 熟悉项目结构3.2.2 Git版本控制3.2.3 数据库环境搭建3.2.4 前…

【分布式】——分布式事务

分布式事务 ⭐⭐⭐⭐⭐⭐ Github主页&#x1f449;https://github.com/A-BigTree 笔记链接&#x1f449;https://github.com/A-BigTree/tree-learning-notes ⭐⭐⭐⭐⭐⭐ Spring专栏&#x1f449;https://blog.csdn.net/weixin_53580595/category_12279588.html SpringMVC专…

前端超分辨率技术应用:图像质量提升与场景实践探索-设计篇

超分辨率&#xff01; 引言 在数字化时代&#xff0c;图像质量对于用户体验的重要性不言而喻。随着显示技术的飞速发展&#xff0c;尤其是移动终端视网膜屏幕的广泛应用&#xff0c;用户对高分辨率、高质量图像的需求日益增长。然而&#xff0c;受限于网络流量、存储空间和图像…

抖音视频关键词无水印下载软件|手机网页视频批量提取工具

全新视频关键词无水印下载软件&#xff0c;助您快速获取所需视频&#xff01; 随着时代的发展&#xff0c;视频内容已成为人们获取信息和娱乐的重要途径。为了方便用户获取所需视频&#xff0c;推出了一款功能强大的视频关键词无水印下载软件。该软件主要功能包括关键词批量提取…

SAP gui 组服务器 提示 Error service sapmsPRD unknown

/etc/hosts 追加IP地址和域名的配对关系 /etc/services 追加 sapms[sid] 3601/tcp

岭师大数据技术原理与应用-序章-软工版

HeZaoCha-CSDN博客 序章—软工版 一、环境介绍1. VMware Workstation Pro2. CentOS3. Java4. Hadoop5. HBase6. MySQL7. Hive 二、系统安装1. 虚拟网络编辑器2. 操作系统安装 三、结尾 先说说哥们写这系列博客的原因&#xff0c;本来学完咱也没想着再管部署这部分问题的说&…

自动化测试 —— Pytest fixture及conftest详解

前言 fixture是在测试函数运行前后&#xff0c;由pytest执行的外壳函数。fixture中的代码可以定制&#xff0c;满足多变的测试需求&#xff0c;包括定义传入测试中的数据集、配置测试前系统的初始状态、为批量测试提供数据源等等。fixture是pytest的精髓所在&#xff0c;类似u…

前端的拖拽序列(drag)

html和css代码如下 <style>.item {width: 200px;height: 50px;background: rgb(15, 226, 219);margin: 10px 0;padding-left: 20px;border-radius: 10px;line-height: 50px;}.item.move {background: transparent;color: transparent;border: 1px dashed #ccc;}</sty…

201基于matlab的成绩管理系统

基于matlab的成绩管理系统。自带的GUI界面设计了一个成绩管理界面&#xff0c;可进行成绩的载入、查询、绘图、求平均分。可更改自己的数据进行录入。包含作业文档。程序已调通&#xff0c;可直接运行。 201 matlab 成绩管理系统 GUI - 小红书 (xiaohongshu.com)

JAVA面试八股文之集合

JAVA集合相关 集合&#xff1f;说一说Java提供的常见集合&#xff1f;hashmap的key可以为null嘛&#xff1f;hashMap线程是否安全, 如果不安全, 如何解决&#xff1f;HashSet和TreeSet&#xff1f;ArrayList底层是如何实现的&#xff1f;ArrayList listnew ArrayList(10)中的li…

常用的8个应用和中间件的Docker运行示例

文章目录 1、Docker Web 管理工具 portainer2、在线代码编辑器 Code Server3、MySQL4、Redis5、Nginx6、PostgreSQL7、媒体管理工具 Dim8、Gitlab 1、Docker Web 管理工具 portainer Portainer 是一个轻量级的管理 UI &#xff0c;可让你轻松管理不同的 Docker 环境&#xff0…