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

【每日一题】得到山形数组的最少删除次数

文章目录

  • 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 即为最后需要返回的答案。

最长递增子序列

如何计算 presuf

presuf 的计算过程类似。先来看一下 pre 的计算。维护数组 prepre[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),更新 presuf 的时间复杂度都为 O(nlogn),更新答案的时间复杂度为 O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n),额外占用的空间为数组 presufg。空间复杂度: O ( n ) O(n) O(n),额外占用的空间为数组 presufg


写在最后

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

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

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

相关文章:

【每日一题】得到山形数组的最少删除次数

文章目录 Tag题目来源解题思路方法一&#xff1a;最长递增子序列 写在最后 Tag 【最长递增子序列】【数组】【2023-12-22】 题目来源 1671. 得到山形数组的最少删除次数 解题思路 方法一&#xff1a;最长递增子序列 前后缀分解 根据前后缀思想&#xff0c;以 nums[i] 为山…...

2023年,为什么汽车依然有很多小毛病?

汽车出现小毛病是一个复杂的问题&#xff0c;其原因涉及到汽车本身的设计、制造质量、维护保养以及使用环境等多个方面。只有汽车制造商、车主和社会各界共同努力&#xff0c;才能够减少汽车的小毛病&#xff0c;提高汽车的可靠性和安全性。 比如&#xff0c;汽车的维护和保养…...

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实验报告十一、自定义类模拟三维向量及其运算

一、实验目的&#xff1a; 1、了解如何定义一个类。 2、了解如何定义类的私有数据成员和成员方法。 3、了解如何使用自定义类实例化对象。 二、实验内容&#xff1a; 定义一个三维向量类&#xff0c;并定义相应的特殊方法实现两个该类对象之间的加、减运算&#xff08;要…...

机器学习 | 聚类Clustering 算法

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

IntelliJ IDEA 2023.3 新功能介绍

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

2. 行为模式 - 命令模式

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

Java智慧工地源码 SAAS智慧工地源码 智慧工地管理可视化平台源码 带移动APP

一、系统主要功能介绍 系统功能介绍&#xff1a; 【项目人员管理】 1. 项目管理&#xff1a;项目名称、施工单位名称、项目地址、项目地址、总造价、总面积、施工准可证、开工日期、计划竣工日期、项目状态等。 2. 人员信息管理&#xff1a;支持身份证及人脸信息采集&#…...

php学习02-php标记风格

<?php echo "这是xml格式风格" ?><script language"php">echo 脚本风格标记 </script><% echo "这是asp格式风格" %>推荐使用xml格式风格 如果要使用简短风格和ASP风格&#xff0c;需要在php.ini中对其进行配置&#…...

13.1 jar文件

13.1 jar文件 java归档&#xff08;JAR&#xff09;文件&#xff0c;将应用程序打包后仅提供的单独文件&#xff0c;可包含类文件&#xff0c;也可包含图片、声音等其他类型文件。 JAR文件使用了大家熟悉的Zip压缩格式&#xff0c;pack200为通常的zip压缩算法&#xff0c;对类…...

论文阅读:Long-Term Visual Simultaneous Localization and Mapping

论文摘要指出&#xff0c;为了在长期变化的环境中准确进行定位&#xff0c;提出了一种新型的长期视觉SLAM&#xff08;同步定位与地图构建&#xff09;系统&#xff0c;该系统具备地图预测和动态物体移除功能。系统首先设计了一个高效的视觉点云匹配算法&#xff0c;将2D像素信…...

Docker 学习总结(80)—— 轻松驾驭容器,玩转 LazyDocker

前言 LazyDocker 是一个用户友好的命令行工具,简化了 Docker 的管理。它能够通过单一命令执行常见的 Docker 任务,如启动、停止、重启和移除容器。LazyDocker 还能轻松查看日志、清理未使用的容器和镜像,并自定义指标。 简绍 LazyDocker 是一个用户友好的 CLI 工具,可以轻…...

Android 13 - Media框架(24)- MediaCodecList

这一节我们要了解 MediaCodecList 中的信息是如何加载的&#xff0c;以及这些信息是如何使用到的。 // 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,随着输入&#xff0c;把值存维护在状态里&#xff0c;需要用的时候去状态里取值&#xff08;推荐&#xff0c;避免了过渡使用ref&#xff09;非受控组件——页面中所有输入类的DOM&#xff0c;现用现取…...

研究生课程 |《数值分析》复习

搭配往年真题册食用最佳。...

55 回溯算法解黄金矿工问题

问题描述&#xff1a;你要开发一座金矿&#xff0c;地质学家已经探明了这座金矿中的资源分布&#xff0c;并用大小为m*n的网格grid进行了标注&#xff0c;每个单元格中的整数就表示这一单元格中的黄金数量&#xff1b;如果单元格是空的&#xff0c;那么就是0&#xff0c;为了使…...

[笔记]ByteBuffer垃圾回收

参考&#xff1a;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…...

法线贴图实现衣服上皱褶特效

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 法线贴图在3D建模中扮演着重要的角色&#xff0c;它通过模拟表面的微…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...