[二分查找]LeetCode1964:找出到每个位置为止最长的有效障碍赛跑路线

本文涉及的基础知识点

二分查找算法合集

作者推荐

动态规划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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/209202.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

uni-app 微信小程序之自定义圆形 tabbar

文章目录 1. 自定义tabbar效果2. pages新建tabbar页面3. tabbar 页面结构4. tabbar 页面完整代码 1. 自定义tabbar效果 2. pages新建tabbar页面 首先在 pages.json 文件中&#xff0c;新建一个 tabbar 页面 "pages": [ //pages数组中第一项表示应用启动页&#xff…

如何快速选出一支好股票?

俗话说得好&#xff1a;股票选得好&#xff0c;收益少不了&#xff01;不用多说&#xff0c;相信大伙儿都知道选一支好股票究竟有多重要。 但是选股可不像咱们去菜市场买菜一样&#xff0c;看着顺眼就成。选股&#xff0c;其实是一个专业性特别强的技术活儿。 目前最常用的选股…

vscode如何在没有网络的情况下安装插件

vscode如何在没有网络的情况下安装插件 start 遇到没有网络的电脑&#xff0c;无法直接从插件市场安装vscode的插件。写一下 vscode 插件离线安装的方法. 解决方案 目标电脑没有可以安装插件的网络&#xff0c;那我们只能在有网络的环境下载好我们的插件。然后拷贝软件到无…

SHAP(三):在解释预测模型以寻求因果见解时要小心

SHAP&#xff08;三&#xff09;&#xff1a;在解释预测模型以寻求因果见解时要小心 与 Microsoft 的 Eleanor Dillon、Jacob LaRiviere、Scott Lundberg、Jonathan Roth 和 Vasilis Syrgkanis 合作撰写的关于因果关系和可解释机器学习的文章。 当与 SHAP 等可解释性工具配合…

一个简单的参数帮助框架,c实现

文章目录 具体实现如下&#xff1a; #include <stdio.h> #include <stdlib.h> #include <string.h> void print_help(char *argv[]) { printf("Usage: %s [options]\n", argv[0]); printf("Options:\n"); printf(" -h, -…

鉴源实验室 | 汽车网络安全攻击实例解析(三)

作者 | 张璇 上海控安可信软件创新研究院工控网络安全组 来源 | 鉴源实验室 社群 | 添加微信号“TICPShanghai”加入“上海控安51fusa安全社区” 引言&#xff1a;随着现代汽车技术的迅速发展&#xff0c;车辆的进入和启动方式经历了显著的演变。传统的物理钥匙逐渐被无钥匙进…

Seaborn图形可视化基础_Python数据分析与可视化

Seaborn图形可视化基础 Seaborn可视化Seaborn与Matplotlib Seaborn可视化 即使matplotlib已经如此强大了&#xff0c;但是不得不承认它不支持的功能还有很多。 例如&#xff1a; 2.0之前的版本的默认配置样式绝对不是用户的最佳选择&#xff1b; matplotlib的API比较底层。虽…

第十节HarmonyOS 常用基础组件-Image

一、组件介绍 组件&#xff08;Component&#xff09;是界面搭建与显示的最小单位&#xff0c;HarmonyOS ArkUI声名式为开发者提供了丰富多样的UI组件&#xff0c;我们可以使用这些组件轻松的编写出更加丰富、漂亮的界面。 组件根据功能可以分为以下五大类&#xff1a;基础组件…

Selenium+Python自动化测试之验证码处理

两种方式&#xff1a; 验证码识别技术 (很难达到100%) 添加Cookie &#xff08;*****五星推荐&#xff09; 方式一&#xff1a;验证码识别技术 逻辑方式&#xff1a; 1&#xff1a;打开验证码所在页面&#xff0c;截图。获取验证码元素坐标&#xff0c;剪切出验证码图片&…

Pandas进阶:文本处理

引言 文本的主要两个类型是string和object。如果不特殊指定类型为string&#xff0c;文本类型一般为object。 文本的操作主要是通过访问器str 来实现的&#xff0c;功能十分强大&#xff0c;但使用前需要注意以下几点。 访问器只能对Series数据结构使用。 除了常规列变量df.c…

对el-select封装成组件使用

效果与直接使用el-select一样&#xff0c;多处用el-select显得代码冗余就进行了封装 效果图&#xff1a; el-select封装&#xff1a; <template><div class"my-select"><el-selectv-model"person.modelValue":placeholder"placehold…

H5 Canvas 打飞机青春版

没事儿写写练习一下&#xff0c;说不准哪天就用到今天所用到的知识点了呢。 在线链接 https://linyisonger.github.io/H5.Examples/?name./053.%E9%A3%9E%E6%9C%BA%E5%A4%A7%E6%88%98.html 功能清单 循环滚动背景 矩形碰撞 随机生成敌人 飞机左右移动 苹果屏蔽长按 移动端屏…

京东数据运营-京东数据开放平台-鲸参谋10月粮油调味市场品牌店铺销售数据分析

鲸参谋监测的京东平台10月份料油调味市场销售数据已出炉&#xff01; 根据鲸参谋数据显示&#xff0c;今年10月份&#xff0c;京东平台粮油调味市场的销量将近4600万&#xff0c;环比增长约10%&#xff0c;同比降低约20%&#xff1b;销售额将近19亿&#xff0c;环比增长约4%&am…

(C++)三数之和--双指针法

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 算法原理 双指针法&#xff0c;不一定是说就要使用指针&#xff0c;只是一种形象的说法&#xff0c;在数组中&#xff0c;我们一般将数组下标当做指针。我们首先对数组进行排序&#xff0c;从左向右标定一个下标i&#xff0…

LED屏幕信息安全如何预防?

随着科技的不断进步&#xff0c;LED屏幕在我们生活和工作中扮演着越来越重要的角色&#xff0c;然而&#xff0c;随之而来的是信息安全面临的挑战。为了有效预防LED屏幕信息的泄露和被盗取&#xff0c;我们需要采取一系列的安全措施。以下是一些建议&#xff1a; 物理安全措施&…

中国毫米波雷达产业分析6——毫米波雷达行业发展展望

一、行业发展驱动力分析 &#xff08;一&#xff09;需求带动 当前&#xff0c;全球智能化变革浪潮正在汽车、交通、安防、工业、家居、健康监护等诸多产业蓬勃发展&#xff0c;创造了巨大的感知产品增量需求。 在汽车领域&#xff0c;毫米波雷达传感器作为一种非接触…

【无标题】mmocr在云服务器上

这里写目录标题 1、创建虚拟环境2、切换和退出conda虚拟环境3. 显示、复制&#xff08;克隆&#xff09;、删除虚拟环境4、删除环境安装指示中 cd进项目文件夹开始训练模型&#xff08;python XXX.py | tee record.txt 记录训练结果&#xff09;如何在Linux服务器上安装Anacond…

leetcode刷题详解—— 环形子数组的最大和

1. 题目链接&#xff1a;918. 环形子数组的最大和 2. 题目描述&#xff1a; 给定一个长度为 n 的环形整数数组 nums &#xff0c;返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上&#xff0c; nums[i] 的下一个元素是 nums[(…

SAP 如何检查已安装的SAP UI5 版本

第一个方法是直接从FLP中查看 但是部分高版本的FLP中没有这个about&#xff0c; 那么在当前界面可以使用&#xff1a;CTRL ALT SHIFT S 查看当前版本 根据此版本&#xff0c;去进行你的UI5的开发吧

NodeJS(二):npm包管理工具、yarn、npx、pnpm工具等

目录 (一)npm包管理工具 1.了解npm 2.npm的配置文件 常见的配置属性 scripts属性*** 依赖的版本管理 3.npm安装包的细节 4.package-lock文件 5.npm install原理** 6.npm的其他命令 (二) 其他包管理工具 1.yarn工具 基本指令 2.cnpm工具 3.npx工具 (1)执行本地…