#include?<iostream>
#include?<vector>
#include?<stack>
#include?<deque>
using?namespace?std;
//?单调栈
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;
}
//?单调队列
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();?
????}
};
//?二叉堆（大根堆/小根堆）、优先队列
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个节点
????void?swim(int?k)?{
????????while?(k?>?1?&&?less(parent(k),?k))?{
????????????exch(parent(k),?k);
????????????k?=?parent(k);
????????}
????}
????//?下沉第k个节点
????void?sink(int?k)?{
????????while?(left(k)?<=?N)?{
????????????//?默认左子树值较大
????????????int?older?=?left(k);
????????????//?如果右子树存在，并且大于左子树，更新older
????????????if?(right(k)?<=?N?&&?less(older,?right(k)))?{
????????????????older?=?right(k);
????????????}
????????????//?节点k比两个子孩子都大，就不必下沉了
????????????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];
????????//?交换栈顶和栈底最后一个节点
????????exch(1,?N);
????????N--;??//?删除最有一个节点
????????sink(1);??//?下沉栈顶节点
????????return?max;
????}
????//?返回当前队列最大节点
????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;??//?合并左右两测
????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];??//?将排序结果拷回原数组
}
//?二叉树遍历模板
typedef?struct?TreeNode?{
????int?val;
????TreeNode?*left;
????TreeNode?*right;
}?TreeNode;
//?思路：
//?1.遍历
//?2.分解问题
/************?遍历?***********/
//?辅助外部变量
void?traverse(TreeNode?*root)?{
????if?(root?==?NULL)
????????return;
????
????/******?前序遍历位置?******/
????traverse(root->left);
????/******?中序遍历位置?******/
????traverse(root->right);
????/******?后续遍历位置?******/
}
/************?分解问题?***********/
//?函数定义：输入以root为根的二叉树，返回这颗二叉树的最大深度
int?MaxDepth(TreeNode?*root)?{
????if?(root?==?NULL)
????????return?0;
????/******?前序遍历位置?******/
????int?ldep?=?MaxDepth(root->left);
????/******?中序遍历位置?******/
????int?rdep?=?MaxDepth(root->right);
????/******?后序遍历位置?******/
????return?max(ldep,?rdep)?+?1;
}
//?二叉搜索树
//?特性：所有左子树节点均小于根节点，所有右子树节点均大于根节点
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;
}
//?动态规划
//?1最优解（最大或最小值）
//?2方案总数
//?3可行性
//?4最长子数组
//?5最长子序列
//?6背包系列问题
//?7打家劫舍系列问题
//?8股票交易系列问题
//?二分算法模板
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;
}
//?快速排序
//?并查集
//?字典树
//?前缀和?树状数组