通过枚举最小（最大）值不重复、不遗漏枚举所有子数组
| 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); } }
二分查找的进一步优化
| 子状态都单调递增或单调递减 |
| 一，插入也是有序，直接栈顶插入。二，淘汰无效状态后，直接栈顶插入。 |
| 二，要查询的值是被淘汰的元素。二，要查询的值是栈顶元素。 |
最小（最大）字典序
其它
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++ 实现。
