作者推薦

map|動態(tài)規(guī)劃|單調(diào)棧|LeetCode975:奇偶跳

通過枚舉最小（最大）值不重復(fù)、不遺漏枚舉所有子數(shù)組

C++算法：美麗塔O(n)解法單調(diào)棧	左右尋找第一個小于maxHeight[i]的left,right，[left,right]直接的高度都是maxHeight[i] 可以用封裝的類，可以理解為枚舉山頂這個子數(shù)組
【單調(diào)棧]LeetCode84: 柱狀圖中最大的矩形
【單調(diào)?！俊緟^(qū)間合并】LeetCode85:最大矩形
【單調(diào)棧】LeetCode2334:元素值大于變化閾值的子數(shù)組
【單調(diào)?！縇eetCode:2818操作使得分最大
【前綴和】【單調(diào)?！縇eetCode2281:巫師的總力量和
map 動態(tài)規(guī)劃 單調(diào)棧 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<>()); 結(jié)果：右邊界從左向右第一個大于當(dāng)前值，左邊界從右向左第一個大于等于當(dāng)前值

原數(shù)組	左邊界	右邊界
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<>());
結(jié)果：右邊界從左向右第一個大于等于當(dāng)前值，左邊界從右向左第一個大于當(dāng)前值
.|原數(shù)組 | 左邊界 | 右邊界|
|–|–|–|
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<>());
結(jié)果：右邊界從左向右第一個小于當(dāng)前值，左邊界從右向左第一個小于等于當(dāng)前值
.|原數(shù)組 | 左邊界 | 右邊界|
|–|–|–|
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<>());
結(jié)果：右邊界從左向右第一個小于等于當(dāng)前值，左邊界從右向左第一個小于當(dāng)前值
.|原數(shù)組 | 左邊界 | 右邊界|
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 << "數(shù)組值：";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 << "數(shù)組值：";CConsole::Out(nums);std::cout << "左邊界：";CConsole::Out(ri.m_vLeft);std::cout << "左邊界：";CConsole::Out(ri.m_vRight);}
}

二分查找的進(jìn)一步優(yōu)化

子狀態(tài)都單調(diào)遞增或單調(diào)遞減
一，插入也是有序，直接棧頂插入。二，淘汰無效狀態(tài)后，直接棧頂插入。
二，要查詢的值是被淘汰的元素。二，要查詢的值是棧頂元素。

【單調(diào)?！縇eetCode1776:車隊
【單調(diào)棧】LeetCode:1944隊列中可以看到的人數(shù)

最小（最大）字典序

【單調(diào)棧 】LeetCode321:拼接最大數(shù)
【單調(diào)?！縇eetCode2030:含特定字母的最小子序列

其它

【單調(diào)棧】【二分查找】LeetCode: 2454.下一個更大元素 IV
【map】【單調(diào)棧 】LeetCode768: 最多能完成排序的塊 II

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)

下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。
子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用C++ 實(shí)現(xiàn)。