【每日一题】得到山形数组的最少删除次数
文章目录
- Tag
- 题目来源
- 解题思路
- 方法一:最长递增子序列
- 写在最后
Tag
【最长递增子序列】【数组】【2023-12-22】
题目来源
1671. 得到山形数组的最少删除次数

解题思路
方法一:最长递增子序列
前后缀分解
根据前后缀思想,以 nums[i]
为山顶的山形数组可以看成 nums[i]
左侧以其作为结尾的最长递增子序列,我们记左侧的最长递增子序列的长度为 pre[i]
,拼接上 nums[i]
右侧以其作为结尾的最长递减子序列,我们记右侧的最长递减子序列的长度为 suf[i]
,此时以 nums[i]
为山顶的山形数组长度为:
p r e [ i ] + s u f [ i ] − 1 pre[i] + suf[i] - 1 pre[i]+suf[i]−1
我们枚举所有的 nums[i]
,计算所有的最长山顶数组长度 maxLen
,最后需要删除的数组元素长度为 n - maxLen
即为最后需要返回的答案。
最长递增子序列
如何计算 pre
和 suf
?
pre
和 suf
的计算过程类似。先来看一下 pre
的计算。维护数组 pre
,pre[i]
表示以 nums[i]
作为结尾的最长递增子序列的长度;维护辅助数组 g
,表示以当前元素 nums[i]
结尾的最长递增子序列数组。
遍历数组 nums
,当前遍历的元素为 nums[i]
记为 x
,在数组 g 中使用二分查找找到第一个大于 x
的元素,对应的位置为 it - g.begin() + 1
:
- 更新
pre[i] = it - g.begin() + 1
; - 如果 x 不在 g 中,则将 x 加入 g;否则将 x 更新到 g 中相应的位置。
在 suf
的计算过程中,我们从后往前遍历数组 nums
,就是找最长的递增子序列,于是计算过程和 pre
的计算类似。
remark1:因为山峰不可能在数组首和尾两个位置出现,那么在遍历所有山峰的范围
[0, n-1]
时,需要先做判断pre[i] >= 2 && suf[i] >= 2
。
remark2:可以先计算
suf
,然后一起计算pre
和更新答案的,留给读者自己实现。
算法
class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {int n = nums.size();vector<int> pre(n), g;for (int i = 0; i < n; ++i) {int x = nums[i];auto it = lower_bound(g.begin(), g.end(), x);pre[i] = it - g.begin() + 1;if (it == g.end()) {g.push_back(x);}else {*it = x;}}vector<int> suf(n);g.clear();for (int i = n - 1; i >= 0; --i) {int x = nums[i];auto it = lower_bound(g.begin(), g.end(), x);suf[i] = it - g.begin() + 1;if (it == g.end()) {g.push_back(x);}else {*it = x;}}int mx = 0;for (int i = 1; i < n - 1; ++i) {mx = max(mx, pre[i] + suf[i] - 1);}return n - mx;}
};
复杂度分析
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),更新 pre
和 suf
的时间复杂度都为 O(nlogn)
,更新答案的时间复杂度为 O ( n ) O(n) O(n)。
空间复杂度: O ( n ) O(n) O(n),额外占用的空间为数组 pre
、suf
和 g
。空间复杂度: O ( n ) O(n) O(n),额外占用的空间为数组 pre
、suf
和 g
。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
相关文章:

【每日一题】得到山形数组的最少删除次数
文章目录 Tag题目来源解题思路方法一:最长递增子序列 写在最后 Tag 【最长递增子序列】【数组】【2023-12-22】 题目来源 1671. 得到山形数组的最少删除次数 解题思路 方法一:最长递增子序列 前后缀分解 根据前后缀思想,以 nums[i] 为山…...
2023年,为什么汽车依然有很多小毛病?
汽车出现小毛病是一个复杂的问题,其原因涉及到汽车本身的设计、制造质量、维护保养以及使用环境等多个方面。只有汽车制造商、车主和社会各界共同努力,才能够减少汽车的小毛病,提高汽车的可靠性和安全性。 比如,汽车的维护和保养…...

yocto系列讲解[实战篇]93 - 添加Qtwebengine和Browser实例
By: fulinux E-mail: fulinux@sina.com Blog: https://blog.csdn.net/fulinus 喜欢的盆友欢迎点赞和订阅! 你的喜欢就是我写作的动力! 目录 概述集成meta-qt5移植过程中的问题问题1:virtual/libgl set to mesa, not mesa-gl问题2:dmabuf-server-buffer tries to use undecl…...

Python实验报告十一、自定义类模拟三维向量及其运算
一、实验目的: 1、了解如何定义一个类。 2、了解如何定义类的私有数据成员和成员方法。 3、了解如何使用自定义类实例化对象。 二、实验内容: 定义一个三维向量类,并定义相应的特殊方法实现两个该类对象之间的加、减运算(要…...

机器学习 | 聚类Clustering 算法
物以类聚人以群分。 什么是聚类呢? 1、核心思想和原理 聚类的目的 同簇高相似度 不同簇高相异度 同类尽量相聚 不同类尽量分离 聚类和分类的区别 分类 classification 监督学习 训练获得分类器 预测未知数据 聚类 clustering 无监督学习,不关心类别标签 …...

IntelliJ IDEA 2023.3 新功能介绍
IntelliJ IDEA 2023.3 在众多领域进行了全面的改进,引入了许多令人期待的功能和增强体验。以下是该版本的一些关键亮点: IntelliJ IDEA mac版下载 macappbox.com/a/intellij-idea-for-mac.html 1. AI Assistant 的全面推出 IntelliJ IDEA 2023.3 中&am…...

2. 行为模式 - 命令模式
亦称: 动作、事务、Action、Transaction、Command 意图 命令模式是一种行为设计模式, 它可将请求转换为一个包含与请求相关的所有信息的独立对象。 该转换让你能根据不同的请求将方法参数化、 延迟请求执行或将其放入队列中, 且能实现可撤销…...

Java智慧工地源码 SAAS智慧工地源码 智慧工地管理可视化平台源码 带移动APP
一、系统主要功能介绍 系统功能介绍: 【项目人员管理】 1. 项目管理:项目名称、施工单位名称、项目地址、项目地址、总造价、总面积、施工准可证、开工日期、计划竣工日期、项目状态等。 2. 人员信息管理:支持身份证及人脸信息采集&#…...

php学习02-php标记风格
<?php echo "这是xml格式风格" ?><script language"php">echo 脚本风格标记 </script><% echo "这是asp格式风格" %>推荐使用xml格式风格 如果要使用简短风格和ASP风格,需要在php.ini中对其进行配置&#…...
13.1 jar文件
13.1 jar文件 java归档(JAR)文件,将应用程序打包后仅提供的单独文件,可包含类文件,也可包含图片、声音等其他类型文件。 JAR文件使用了大家熟悉的Zip压缩格式,pack200为通常的zip压缩算法,对类…...
论文阅读:Long-Term Visual Simultaneous Localization and Mapping
论文摘要指出,为了在长期变化的环境中准确进行定位,提出了一种新型的长期视觉SLAM(同步定位与地图构建)系统,该系统具备地图预测和动态物体移除功能。系统首先设计了一个高效的视觉点云匹配算法,将2D像素信…...

Docker 学习总结(80)—— 轻松驾驭容器,玩转 LazyDocker
前言 LazyDocker 是一个用户友好的命令行工具,简化了 Docker 的管理。它能够通过单一命令执行常见的 Docker 任务,如启动、停止、重启和移除容器。LazyDocker 还能轻松查看日志、清理未使用的容器和镜像,并自定义指标。 简绍 LazyDocker 是一个用户友好的 CLI 工具,可以轻…...
Android 13 - Media框架(24)- MediaCodecList
这一节我们要了解 MediaCodecList 中的信息是如何加载的,以及这些信息是如何使用到的。 // static sp<IMediaCodecList> MediaCodecList::getLocalInstance() {Mutex::Autolock autoLock(sInitMutex);if (sCodecList nullptr) {MediaCodecList *codecList n…...

【稳定检索|投稿优惠】2024年交通运输与能源动力国际学术会议(IACTEP 2024)
2024年交通运输与能源动力国际学术会议(IACTEP 2024) 2024 International Academic Conference on Transportation and Energy Power(IACTEP) 一、【会议简介】 2024年交通运输与能源动力国际学术会议(IACTEP 2024)将在美丽的三亚盛大启幕。本次会议将聚焦交通运输与能源动力等…...

React学习计划-React16--React基础(三)收集表单数据、高阶函数柯里化、类的复习
1. 收集表单数据 包含表单的组件分类 受控组件——页面中所有输入类的DOM,随着输入,把值存维护在状态里,需要用的时候去状态里取值(推荐,避免了过渡使用ref)非受控组件——页面中所有输入类的DOM,现用现取…...

研究生课程 |《数值分析》复习
搭配往年真题册食用最佳。...
55 回溯算法解黄金矿工问题
问题描述:你要开发一座金矿,地质学家已经探明了这座金矿中的资源分布,并用大小为m*n的网格grid进行了标注,每个单元格中的整数就表示这一单元格中的黄金数量;如果单元格是空的,那么就是0,为了使…...

[笔记]ByteBuffer垃圾回收
参考:https://blog.csdn.net/lom9357bye/article/details/133702169 public static void main(String[] args) throws Throwable {List<Object> list new ArrayList<>();Thread thread new Thread(() -> {ByteBuffer byteBuffer ByteBuffer.alloc…...
c++ opencv中unsigned char *、Mat、Qimage互相转换
unsigned char * 转Mat unsinged char * data img.data; Mat mat (h,w,cv_8UC3,data,0);void * 转Qimage uchar * bit (uchar*)pRknnInputData; QImage image QImage(bit, 2048,1536, QImage::Format_RGB888);qimage转Mat QImage image QImage (MODEL_INPUT_WIDTH_SIZE,MODE…...

法线贴图实现衣服上皱褶特效
在线工具推荐: 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 法线贴图在3D建模中扮演着重要的角色,它通过模拟表面的微…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...

Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...