首页 > 其他分享 >单调栈分类、封装和总结

单调栈分类、封装和总结

时间:2024-01-02 12:38:01浏览次数:24  
标签:总结 std 封装 边界 nums CRangIndex 单调 sta


作者推荐

map|动态规划|单调栈|LeetCode975:奇偶跳

通过枚举最小(最大)值不重复、不遗漏枚举所有子数组


C++算法:美丽塔O(n)解法单调栈

左右寻找第一个小于maxHeight[i]的left,right,[left,right]直接的高度都是maxHeight[i] 可以用封装的类,可以理解为枚举山顶这个子数组

【单调栈]LeetCode84: 柱状图中最大的矩形

【单调栈】【区间合并】LeetCode85:最大矩形

【单调栈】LeetCode2334:元素值大于变化阈值的子数组

【单调栈】LeetCode:2818操作使得分最大

【前缀和】【单调栈】LeetCode2281:巫师的总力量和

map 动态规划 单调栈 LeetCode975:奇偶跳

封装类

class CRangIndex
{
public:
	template<class _Pr>
	CRangIndex(int iVectorSize, _Pr CurIndexCmpStackTopIndex)
	{
		m_c = iVectorSize;
		m_vLeft.assign(m_c, -1);
		m_vRight.assign(m_c, m_c);
		stack<int> sta;
		for (int i = 0; i < m_c; i++)
		{
			while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top())))
			{
				m_vRight[sta.top()] = i;
				sta.pop();
			}
			if (sta.size())
			{
				m_vLeft[i] = sta.top();
			}
			sta.emplace(i);
		}
	}

	template<class _Pr>
	CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue)
	{
		m_c = nums.size();
		m_vLeft.assign(m_c, -1);
		m_vRight.assign(m_c, m_c);
		stack<int> sta;
		for (int i = 0; i < m_c; i++)
		{
			while (sta.size() && (CurValueCmpStackTopValue(nums[i], nums[sta.top()])))
			{
				m_vRight[sta.top()] = i;
				sta.pop();
			}
			if (sta.size())
			{
				m_vLeft[i] = sta.top();
			}
			sta.emplace(i);
		}
	}
	int m_c;
	vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};

测试用例

大于

CRangIndex ri(nums, std::greater<>()); 结果:右边界从左向右第一个大于当前值,左边界从右向左第一个大于等于当前值

原数组

左边界

右边界

1 2 3 3 4

-1 -1 -1 2 -1

1 2 4 4 5

8 7 3 4

-1 0 1 1

4 4 3 4

大于等于

CRangIndex ri(nums, std::greater_equal<>());
结果:右边界从左向右第一个大于等于当前值,左边界从右向左第一个大于当前值
.|原数组 | 左边界 | 右边界|
|–|–|–|
1 2 3 3 4|-1 -1 -1 -1 -1|1 2 3 4 5
8 7 3 4| -1 0 1 1|4 4 3 4

小于

CRangIndex ri(nums, std::less<>());
结果:右边界从左向右第一个小于当前值,左边界从右向左第一个小于等于当前值
.|原数组 | 左边界 | 右边界|
|–|–|–|
1 2 3 3 4|-1 0 1 2 3|5 5 5 5 5
8 7 3 4 |-1 -1 -1 2|1 2 4 4

小于等于

CRangIndex ri(nums, std::less_equal<>());
结果:右边界从左向右第一个小于等于当前值,左边界从右向左第一个小于当前值
.|原数组 | 左边界 | 右边界|
1 2 3 3 4|-1 0 1 1 3|5 5 3 5 5
8 7 3 4| -1 -1 -1 2|1 2 4 4

int main()
{
	vector<int> nums;
	{
		nums = { 1,2,3,3,4 };
		CRangIndex ri(nums, std::less_equal<>());
		std::cout << "数组值:";
		CConsole::Out(nums);
		std::cout << "左边界:";
		CConsole::Out(ri.m_vLeft);
		std::cout << "左边界:";
		CConsole::Out(ri.m_vRight);
	}

	{
		nums = { 8,7,3,4 };
		CRangIndex ri(nums, std::less_equal<>());
		std::cout << "数组值:";
		CConsole::Out(nums);
		std::cout << "左边界:";
		CConsole::Out(ri.m_vLeft);
		std::cout << "左边界:";
		CConsole::Out(ri.m_vRight);
	}
}

二分查找的进一步优化

子状态都单调递增或单调递减

一,插入也是有序,直接栈顶插入。二,淘汰无效状态后,直接栈顶插入。

二,要查询的值是被淘汰的元素。二,要查询的值是栈顶元素。

【单调栈】LeetCode1776:车队【单调栈】LeetCode:1944队列中可以看到的人数

最小(最大)字典序

【单调栈 】LeetCode321:拼接最大数【单调栈】LeetCode2030:含特定字母的最小子序列

其它

【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV

【map】【单调栈 】LeetCode768: 最多能完成排序的块 II



相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

我想对大家说的话

闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。

子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。

如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法C++ 实现。

单调栈分类、封装和总结_枚举子数组


标签:总结,std,封装,边界,nums,CRangIndex,单调,sta
From: https://blog.51cto.com/u_15724537/9067522

相关文章

  • 坚果的2023年终总结-激流勇进的一年
    坚果的2023年终总结-激流勇进的一年作者:坚果华为HDE,润开鸿生态技术专家,,坚果派创始人,OpenHarmony布道师,开发者联盟优秀讲师,2023年开源之夏导师,2023年OpenHarmony应用创新赛导师,OpenHarmony金融应用创新赛导师,RISC-V+OpenHarmony应用创意赛导师,OpenHarmony三方库贡献者,开放原子开源......
  • 【2023年终总结:轻舟已过万重山】
    2023年终总结回顾先回顾一下2023年整体所做的一些事情在2023年初的时候,也就是研一下学期,在学习实验室中所做的工作也就是写java项目,由于我加入的实验室更偏向于开发,因此研一一整年也没有看论文,一整年的任务也就是在做Java开发,因此在写了几个项目之后,发现项目中并没有用到......
  • Linux 静态链接和动态链接相关知识点总结
    staticlibrary和sharedlibrary的区别静态库(StaticLibrary)和共享库(SharedLibrary)是两种不同的库的形式,它们在链接和加载的方式上有一些关键的区别。静态库(StaticLibrary):文件格式:静态库的代码和数据在编译时被复制到程序的可执行文件中。文件扩展名:在大多数系统中,静态......
  • 2023-2024-1 20231423《计算机基础与程序设计》第十四周学习总结
    作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2022-2023-1计算机基础与程序设计第十四周作业这个作业的目标《C语言程序设计》第十三章《C语言程序设计》二进制文件和文本文件二进制文件是一种字节序列,没有字符变换,其中的......
  • 学期2023-2024-1 20231409 《计算机基础与程序设计》第十四周学习总结
    学期2023-2024-120231409《计算机基础与程序设计》第十四周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第十四周作业这个作业的目标《C语言程序设计》第13章并完成云班课测试作......
  • 2023-2024-1 20231413 《计算机基础与程序设计》第十四周学习总结
    2023-2024-120231413《计算机基础与程序设计》第十四周学习总结1.作业信息班级:2023-2024-1-计算机基础与程序设计作业要求:2023-2024-1《计算机基础与程序设计》教学进程目标:自学教材:《C语言程序设计》第14章并完成云班课测试作业正文:https://www.cnblogs.com/Kaifazheju......
  • 2023-2024-1 20231410《计算机基础与程序设计》第14周学习总结
    2023-2024-120231410《计算机基础与程序设计》第14周学习总结作业信息这个作业属于哪个课程(https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP)这个作业要求在哪里(https://www.cnblogs.com/rocedu/p/9577842.html#WEEK13)这个作业的目标自学教材《C语言程......
  • 2023-2024-1 20231309 《计算机基础与程序设计》第十四周学习总结
    2023-2024-120231309《计算机基础与程序设计》第十四周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第十四周作业这个作业的目标自学教材《C语言程序设计》第13章并完成云班课测......
  • 2023.12.31——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.ERP明日计划:学习......
  • 2023-2024-1 20231326《计算机基础与程序设计》第十四周学习总结
    2023-2024-120231326《计算机基础与程序设计》第十四周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2022-2023-1计算机基础与程序设计第十四周作业这个作业的目标《C语言程序设计》第十三章作业正文https://www......