南阳南阳新区网站建设,南沙seo培训,总做总结 网站维护的收获,网站数据库连接失败目录 1 知识点2 模板 1 知识点
栈#xff1a;先进后出。先进的就是栈底#xff0c;后进的就是栈顶。后进先出嘛#xff0c;所以在栈顶弹出元素。
队列#xff1a;先进先出。先进的就是队头#xff0c;后进的就是队尾。先进先出嘛#xff0c;所以在队头弹出元素。
单调… 目录 1 知识点2 模板 1 知识点
栈先进后出。先进的就是栈底后进的就是栈顶。后进先出嘛所以在栈顶弹出元素。
队列先进先出。先进的就是队头后进的就是队尾。先进先出嘛所以在队头弹出元素。
单调栈输入数组求每个元素左边的某个元素满足1比它小2离它最近。
//输入数组nums
//输出上述要求的数值
for (int i 0; i nums.size(); i) {while (tt stk[tt] nums[i]) {tt--;}if (tt) {cout stk[tt] ;} else {cout -1 ;}stk[tt] nums[i];
}
cout endl;单调队列求滑动窗口中的最大值或最小值
//输入数组nums区间长度k
//1找到滑动窗口的最小值
int hh 0, tt -1;
for (int i 0; i nums.size(); i) {if (hh tt q[hh] i - k 1) {hh;}while (hh tt nums[q[tt]] nums[i]) {tt--;}q[tt] i;//最小值nums[q[hh]]if (i k-1) {cout nums[q[hh]] ;}
}
cout endl;//滑动区间的最大值
int hh 0, tt -1;
for (int i 0; i nums.size(); i) {if (hh tt q[hh] i - k 1) {hh;}while (hh tt nums[q[tt]] nums[i]) {tt--;}q[tt] i;//最大值nums[q[hh]]if (i k - 1) {cout nums[q[hh]] ;}
}
cout endl;用数组来模拟上述数据结构。
2 模板
一用数组来模拟栈的模板
const int N 1e6 10;
int stk[N], tt 0;//tt表示栈顶下标stk[tt]表示栈顶的值。//1往栈中插入数值x
stk[tt] x;//2删除栈顶元素
tt--;//3栈顶元素的值
stk[tt];//4判断栈是否为空
if (tt 0) {//栈不为空
} else {//栈为空
}二用数组来模拟队列的模板
const int N 1e6 10;
int q[N], hh 0, tt -1;//hh表示队头下标tt表示队尾下标。q[hh]表示队头的值q[tt]表示队尾的值。//1往队列中插入数值x
q[tt] x;//2往队列中删除元素
hh;//3取队头元素
q[hh];//4取队尾元素
q[tt];//5判断队列是否为空
if (hh tt) {//队列不为空
} else {//队列为空
}
