作者推荐

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]。
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49

测试用例

大于

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

大于等于

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);
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

二分查找的进一步优化

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

最小（最大）字典序

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

其它

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
如无特殊说明，本算法用C++ 实现。