LeetCode 1671. 得到山形数组的最少删除次数

2023-12-23 01:20

本文主要是介绍LeetCode 1671. 得到山形数组的最少删除次数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目

1、题目描述

我们定义 arr 是 山形数组 当且仅当它满足:

  • arr.length >= 3
  • 存在某个下标 i (从 0 开始) 满足 0 < i < arr.length - 1 且:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums​ ,请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

2、接口描述

class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {}
};

3、原题链接

1671. 得到山形数组的最少删除次数


二、解题报告

1、思路分析

显然我们找到最长山脉子序列的长度,用原数组长度减去最长山脉子序列的长度就能得到最少删除次数。

对于山脉子序列而言,左边到山峰递增,右边到山峰也递增,那么我们正向反向都求一次最长递增子序列,找到max(pre[i] + suf[i] - 1)就是最长山脉子序列的长度

最终返回原数组长度与其的差即可

2、复杂度

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

3、代码详解

class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {int n = nums.size() , ret = 0;vector<int> dp , pre(n);for(int i = 0 ; i < n ; i++){if(!dp.size() || nums[i] > dp.back())dp.emplace_back(nums[i]) , pre[i] = dp.size();else{auto it = lower_bound(dp.begin() , dp.end() , nums[i]);*it = nums[i];pre[i] = it - dp.begin() + 1;}}dp.clear();for(int i = n - 1 ; i >= 0 ; i--){if(!dp.size() || nums[i] > dp.back()){dp.emplace_back(nums[i]);if(pre[i] >= 2 && dp.size() >= 2)ret = max(ret , (int)dp.size() + pre[i] - 1);}else{auto it = lower_bound(dp.begin() , dp.end() , nums[i]);*it = nums[i];if(pre[i] >= 2 && (it - dp.begin() + 1) >= 2)ret = max(ret , (int)(it - dp.begin()) + pre[i]);}}cout << ret;return nums.size() - ret;}
};

这篇关于LeetCode 1671. 得到山形数组的最少删除次数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/526217

相关文章

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除