本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552:优化了6版的1324模式
题目
你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ,数组长度为 n ,其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间(包含 0 和 n - 1)的下标 i ,在满足下述条件的前提下,请你找出 obstacles 能构成的最长障碍路线的长度:
你可以选择下标介于 0 到 i 之间(包含 0 和 i)的任意个障碍。
在这条路线中,必须包含第 i 个障碍。
你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
除第一个障碍外,路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
返回长度为 n 的答案数组 ans ,其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。
示例 1:
输入:obstacles = [1,2,3,2]
输出:[1,2,3,3]
解释:每个位置的最长有效障碍路线是:
- i = 0: [1], [1] 长度为 1
- i = 1: [1,2], [1,2] 长度为 2
- i = 2: [1,2,3], [1,2,3] 长度为 3
- i = 3: [1,2,3,2], [1,2,2] 长度为 3
示例 2:
输入:obstacles = [2,2,1]
输出:[1,2,1]
解释:每个位置的最长有效障碍路线是: - i = 0: [2], [2] 长度为 1
- i = 1: [2,2], [2,2] 长度为 2
- i = 2: [2,2,1], [1] 长度为 1
示例 3:
输入:obstacles = [3,1,5,6,4,2]
输出:[1,1,2,3,2,2]
解释:每个位置的最长有效障碍路线是: - i = 0: [3], [3] 长度为 1
- i = 1: [3,1], [1] 长度为 1
- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2
参数范围:
n == obstacles.length
1 <= n <= 105
1 <= obstacles[i] <= 107
分析:二分有序映射
时间复杂度
O(nlogn),枚举终点O(n),每个终点二分查找O(logn)。
变量解析
mHeightNum,键是路障搞定,值是以当前路障为终点的最长路障路线。
代码
template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey>
class COrderValueMap
{
public:
void Add (_Kty key, _Ty value)
{
if (bOutSmallKey)
{
if (bValueDdes)
{
AddOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
}
else
{
assert(false);
}
}
else
{
if (bValueDdes)
{
AddNotOutSmall(key, value, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
}
else
{
AddNotOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
}
}
};
std::map<_Kty, _Ty> m_map;
protected:
template<class _Pr1, class _Pr2>
void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2)
{
auto it = m_map.lower_bound(key);
if ((m_map.end() != it) && pr1(it->second, value))
{
return;//被旧值淘汰
}
auto ij = it;
while (it != m_map.begin())
{
–it;
if (pr2(it->second, value))
{
it = m_map.erase(it);
}
}
m_map[key] = value;
}
template<class _Pr1, class _Pr2>
void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 )
{
auto it = m_map.upper_bound(key);
if ((m_map.begin() != it) && pr1(std::prev(it)->second, value))
{
return;//被淘汰
}
auto ij = it;
for (; (m_map.end() != ij) && pr2(ij->second, value); ++ij);
m_map.erase(it, ij);
m_map[key] = value;
};
};
class Solution {
public:
vector longestObstacleCourseAtEachPosition(vector& obstacles) {
COrderValueMap<int, int, true, false> mHeightNum;
vector vRet;
for (const auto& n : obstacles)
{
auto it = mHeightNum.m_map.upper_bound(n);
const int iCurNum = (mHeightNum.m_map.begin() == it) ? 1 : (1 + std::prev(it)->second);
vRet.emplace_back(iCurNum);
mHeightNum.Add(n, iCurNum);
}
return vRet;
}
};
二分有序向量
vLenToMin[i]表示长度为i的路障,终点路障高度为:vLenToMin[i]。如果有相同的路障长度,终点路障高度取最小值。
代码
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> vLenToMin = { 0 };
vector<int> vRet;
for (const auto& n : obstacles)
{
int index = std::upper_bound(vLenToMin.begin(), vLenToMin.end(),n) - vLenToMin.begin();
if (index >= vLenToMin.size())
{
vLenToMin.emplace_back(n);
}
else
{
vLenToMin[index] = min(vLenToMin[index], n);
}
vRet.emplace_back(index);
}
return vRet;
}
};
2023年3月版旧代码
class Solution {
public:
vector longestObstacleCourseAtEachPosition(vector& obstacles) {
std::map<int, int> mHeightNum;
vector vRet;
for (const auto& obs : obstacles)
{
auto it = mHeightNum.upper_bound(obs);
int iNum = 1;
if (mHeightNum.begin() != it)
{
auto tmp = it;
iNum = (–tmp)->second+1;
}
if (mHeightNum.end() != it)
{
if (iNum >= it->second)
{
mHeightNum.erase(it);
}
}
mHeightNum[obs] = iNum;
vRet.push_back(iNum);
}
return vRet;
}
};
2023年7月旧代码
class Solution {
public:
vector longestObstacleCourseAtEachPosition(vector& obstacles) {
std::vector vHeight(obstacles.begin(), obstacles.end());
sort(vHeight.begin(), vHeight.end());
vHeight.erase(std::unique(vHeight.begin(), vHeight.end()), vHeight.end());
std::unordered_map<int, int> mValueToIndex;
for (int i = 0; i < vHeight.size(); i++)
{
mValueToIndex[vHeight[i]] = i;
}
CMaxLineTree tree(mValueToIndex.size());
vector vRet;
for (const auto& n : obstacles)
{
const int index = mValueToIndex[n];
const auto iRet = tree.Query(0, index) + 1;
vRet.emplace_back(iRet);
tree.Modify(index, iRet);
}
return vRet;
}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17