#include?<iostream>
#include?<vector>
#include?<stack>
#include?<deque>

using?namespace?std;

//?單調(diào)棧
vector<int>?nextGreaterElement(vector<int>&?nums)
{
????vector<int>?ans;
????stack<int>?s;
????for?(int?i?=?nums.size()?-?1;?i?>=?0;?i--)?{
????????while?(!s.empty()?&&?s.top()?<?nums[i])?{
????????????s.pop();
????????}
????????ans[i]?=?s.empty()???-1?:?s.top();
????????s.push(nums[i]);
????}
????return?ans;
}

//?單調(diào)隊(duì)列
class?MonotomicQueue{
????deque<int>?data;
public:
????void?push(int?n)?{
????????while?(!data.empty()?&&?data.back()?>?n)?{
????????????data.pop_back();
????????}
????????data.push_back(n);
????}
????void?pop(int?n)?{
????????if?(data.empty()?&&?data.front()?==?n)
????????????data.pop_front();
????}
????int?min()?{
????????return?data.front();?
????}
};

//?二叉堆（大根堆/小根堆）、優(yōu)先隊(duì)列
class?MaxPQ?{
????vector<int>?pq;
????int?N?=?0;??//?大根堆容量
????
????int?parent(int?root)?{
????????return?root?/?2;
????}
????int?left(int?root)?{
????????return?2?*?root;
????}
????int?right(int?root)?{
????????return?2?*?root?+?1;
????}
????
????bool?less(int?i,?int?j)?{
????????return?pq[i]?<?pq[j];
????}
????void?exch(int?i,?int?j)?{
????????swap(pq[i],?pq[j]);
????}
????//?上浮第k個(gè)節(jié)點(diǎn)
????void?swim(int?k)?{
????????while?(k?>?1?&&?less(parent(k),?k))?{
????????????exch(parent(k),?k);
????????????k?=?parent(k);
????????}
????}
????//?下沉第k個(gè)節(jié)點(diǎn)
????void?sink(int?k)?{
????????while?(left(k)?<=?N)?{
????????????//?默認(rèn)左子樹(shù)值較大
????????????int?older?=?left(k);
????????????//?如果右子樹(shù)存在，并且大于左子樹(shù)，更新older
????????????if?(right(k)?<=?N?&&?less(older,?right(k)))?{
????????????????older?=?right(k);
????????????}
????????????//?節(jié)點(diǎn)k比兩個(gè)子孩子都大，就不必下沉了
????????????if?(less(older,?k))?break;
????????????exch(k,?older);
????????????k?=?older;
????????}
????}
????
public:
????void?insert(int?e)?{
????????N++;
????????pq[N]?=?e;
????????swim(N);
????}
????int?delMax()?{
????????int?max?=?pq[1];
????????//?交換棧頂和棧底最后一個(gè)節(jié)點(diǎn)
????????exch(1,?N);
????????N--;??//?刪除最有一個(gè)節(jié)點(diǎn)
????????sink(1);??//?下沉棧頂節(jié)點(diǎn)
????????return?max;
????}
????//?返回當(dāng)前隊(duì)列最大節(jié)點(diǎn)
????int?max()?{
????????return?pq[1];
????}
};

//?歸并排序
vector<int>?temp;
void?merge_sort(vector<int>&?nums,?int?l,?int?r)?{
????if?(l?>=?r)
????????return;
????
????int?mid?=?(r?+?l)?>>?1;
????merge_sort(nums,?l,?mid);?????????//?遞歸排列左半邊
????merge_sort(nums,?mid?+?1,?r);?????//?遞歸排列右半邊
????int?k?=?l,?p1?=?l,?p2?=?mid?+?1;??//?合并左右兩測(cè)
????while?((p1?<=?mid)?||?(p2?<=?r))?{
????????if?((p2?>?r)?||?(p1?<=?mid?&&?nums[p1]?<?nums[p2]))?{
????????????temp[k++]?=?nums[p1++];
????????}?else?{
????????????temp[k++]?=?nums[p2++];
????????}
????}
????for?(int?i?=?l;?i?<=?r;?i++)?nums[i]?=?temp[i];??//?將排序結(jié)果拷回原數(shù)組
}

//?二叉樹(shù)遍歷模板
typedef?struct?TreeNode?{
????int?val;
????TreeNode?*left;
????TreeNode?*right;
}?TreeNode;
//?思路：
//?1.遍歷
//?2.分解問(wèn)題
/************?遍歷?***********/
//?輔助外部變量
void?traverse(TreeNode?*root)?{
????if?(root?==?NULL)
????????return;
????
????/******?前序遍歷位置?******/
????traverse(root->left);
????/******?中序遍歷位置?******/
????traverse(root->right);
????/******?后續(xù)遍歷位置?******/
}
/************?分解問(wèn)題?***********/
//?函數(shù)定義：輸入以root為根的二叉樹(shù)，返回這顆二叉樹(shù)的最大深度
int?MaxDepth(TreeNode?*root)?{
????if?(root?==?NULL)
????????return?0;
????/******?前序遍歷位置?******/
????int?ldep?=?MaxDepth(root->left);
????/******?中序遍歷位置?******/
????int?rdep?=?MaxDepth(root->right);
????/******?后序遍歷位置?******/
????return?max(ldep,?rdep)?+?1;
}

//?二叉搜索樹(shù)
//?特性：所有左子樹(shù)節(jié)點(diǎn)均小于根節(jié)點(diǎn)，所有右子樹(shù)節(jié)點(diǎn)均大于根節(jié)點(diǎn)
int?searchBST(TreeNode?*root,?int?target)?{
????if?(root)
????????return?-1;
????
????if?(root->val?==?target)?{
????????return?root->val;
????}
????if?(root->val?<?target)?{
????????return?searchBST(root->right,?target);
????}
????if?(root->val?>?target)?{
????????return?searchBST(root->left,?target);
????}
????return?-1;
}

//?動(dòng)態(tài)規(guī)劃
//?1最優(yōu)解（最大或最小值）
//?2方案總數(shù)
//?3可行性
//?4最長(zhǎng)子數(shù)組
//?5最長(zhǎng)子序列
//?6背包系列問(wèn)題
//?7打家劫舍系列問(wèn)題
//?8股票交易系列問(wèn)題

//?二分算法模板
int?findTarget(vector<int>&?nums,?int?target)?{
????int?l?=?0,?r?=?nums.size()?-?1;
????while?(l?<=?r)?{
????????int?mid?=?l?+?(r?-?l)?/?2;
????????if?(nums[mid]?>?target)?{
????????????r?=?mid?-?1;
????????}?else?if?(nums[mid]?<?target)?{
????????????l?=?mid?+?1;
????????}?else?{
????????????return?nums[mid];
????????}
????}
????return?-1;
}

//?快速排序

//?并查集

//?字典樹(shù)

//?前綴和?樹(shù)狀數(shù)組文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-794434.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！