作者推荐
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++ 实现。