涉及知识点
二分查找 单调映射
源码下载
点击下载源码
题目
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
参数范围:
1
-104
暴力解法
分析
m_vRet[i],记录以nums[i]结尾的最长严格递增系列。计算m_vRet[i]的方法:nums[j]
下表以{1,2,6,5,4,5}
i |
m_vRet[0,i),加粗表示nums[j] |
m_vRet[i] |
0 |
|
1 |
1 |
1 |
2{1,2} |
2 |
1 2 |
3{1,2,6} |
3 |
1 2 3 |
3{1,2,5} |
4 |
1 2 3 3 |
3{1,2,4} |
5 |
1 2 3 3 3 |
4{1,2,4,5} |
两层循环,分别枚举i和j,故总时间复杂度是O(n2)。
代码
class 服务器托管网Solution {
public:
int lengthOfLIS(vectorint>& nums) {
m_c = nums.size();
m_vRet.resize(m_c);
for (int i = 0; i
{
int iPreLen = 0;
for (int j = 0; j
{
if (nums[j] >= nums[i])
{
continue;
}
iPreLen = max(iPreLen, m_vRet[j]);
}
m_vRet[i] = iPreLen + 1;
}
return *std::max_element(m_vRet.begin(), m_vRet.end());
}
vectorint> m_vRet;
int m_c;
};
有序映射
分析
如果nums[j1] > nums[j2],且m_vRet[j1]
下表以{1,2,6,5,4,5,5}为列来说明,加粗表示新增加,删除线表示删除。
{1,1} |
{1,1},{2,2} |
{1,1},{2,2},{6,3} |
{1,1},{2,2},{5,3}, |
{1,1},{2,2},{4,3}, |
{1,1},{2,2},{4,3},{5,4} |
{1,1},{2,2},{4,3},{5,4} |
代码
class Solution {
public:
int lengthO服务器托管网fLIS(vectorint>& nums) {
m_c = nums.size();
m_vRet.resize(m_c);
std::mapint, int> mValueLen = { {-1000 * 1000,0} };
for (int i = 0; i
{
//计算以nums[i]结尾的最长长度
auto it = mValueLen.lower_bound(nums[i]);
const int iLen = std::prev(it)->second + 1;
m_vRet[i] = iLen;
//如果nums[j] >= nums[j],且长度小于等于删除
auto ij = it;
for (; (ij != mValueLen.end()) && (ij->second ++ij);
mValueLen.erase(it, ij);
//如果nums[i]存在,说明旧值比当前值大,不能处理
if (!mValueLen.count(nums[i]))
{
mValueLen[nums[i]] = iLen;
}
}
return *std::max_element(m_vRet.begin(), m_vRet.end());
}
vectorint> m_vRet;
int m_c;
};
其它
学院课程
基础算法的C++实现课程,请点击下面的CSDN学院的链接。讲义有算法详解。 |
2024年1月15之前完全免费,之后绝大部分免费 |
https://edu.csdn.net/course/detail/38771 |
C#入职培训 |
此课程的目的:让新同事更快完成从学生到C#程序员的转换,更快上手完成C#的开发工作。 |
https://edu.csdn.net/course/detail/38768 |
C++入职培训 |
让新同事更快完成从学生到C++程序员的转换,更快上手完成C++的开发工作。 |
https://edu.csdn.net/course/detail/32049 |
运行验证环境
Win10 VS2022 Ck++17 或win7 VS2019 C++17
每天都补充正能量
好好学习,天天向上。 |
事无终始,无务多业。 |
是故置本不安者,无务丰末。 |
相关下载
如果你时间宝贵,只想看精华,请到CSDN下载频道下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
千兆工业交换机(Gigabit Industrial Switch)是一种用于工业环境的高速以太网交换机,具有以下特性: 1. 高速传输:支持千兆以太网速率(1000Mbps),提供更快的数据传输速度和高带宽。 2. 多端口:通服务器托管网常具有多个…