单调栈
单调栈:栈中数据从栈底至栈顶具有单调性。要求序列中每个元素都必须要进入一次单调栈。由于单调栈的特性,每个元素可能并不会在遍历序列之后仍然保留在单调栈内。
应用:求解 N G E / N L E 、 P G E / P L E NGE/NLE、PGE/PLE NGE/NLE、PGE/PLE问题( N e x t / P r e v i o u s G r e a t e r / L e s s E l e m e n t Next/Previous\ Greater/Less\ Element Next/Previous Greater/Less Element)。
-
G
r
e
a
t
e
r
Greater
Greater类问题:构造单调递减栈
L e s s Less Less类问题:构造单调递增栈 -
P
r
e
v
i
o
u
s
Previous
Previous类问题:以即将入栈的元素为视角看栈顶元素,不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)
N e x t Next Next类问题:以栈顶元素为视角看即将入栈元素,允许即将入栈元素与栈顶元素相同
N G E / N L E NGE/NLE NGE/NLE问题
-
N G E NGE NGE:构造单调递减栈,以栈顶元素为视角看即将入栈元素,允许即将入栈元素与栈顶元素相同
-
N L E NLE NLE:构造单调递增栈,以栈顶元素为视角看即将入栈元素,允许即将入栈元素与栈顶元素相同
//tuple三个数据分别为:data:元素本身 index:元素所在下标 ans:答案所在下标
extern vector<tuple<int,int,int>>v;
extern stack<tuple<int,int,int>>s;
void nge(){
for(int i=0;i<v.size();i++){
if(s.empty()||get<0>(s.top())>=get<0>(v[i])){//nle为<= 允许栈顶元素和即将入栈元素相同
s.push(v[i]);
}else{
while(s.size()&&get<0>(s.top())<get<0>(v[i])){//nle为>
get<2>(v[get<1>(s.top())])=get<1>(v[i]);
s.pop();
}
s.push(v[i]);
}
}
}
P G E / P L E PGE/PLE PGE/PLE问题
- P G E PGE PGE:构造单调递减栈,以入栈元素为视角看栈顶元素,不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)
- P L E PLE PLE:构造单调递增栈,以入栈元素为视角看栈顶元素,不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)
//tuple三个数据分别为:data:元素本身 index:元素所在下标 ans:答案所在下标
extern vector<tuple<int,int,int>>v;
extern stack<tuple<int,int,int>>s;
void pge(){
for(int i=0;i<v.size();i++){
if(s.empty()){
s.push(v[i]);
}else if(get<0>(v[i])<=get<0>(s.top())){//ple为>=
while(get<0>(v[i])==get<0>(s.top())) s.pop();//不允许栈顶元素与即将入栈元素相同
get<2>(v[i])=get<1>(s.top());
s.push(v[i]);
}else{
while(!s.empty()&&get<0>(v[i])>get<0>(s.top())) s.pop();//ple为<
get<2>(v[i])=get<1>(s.top());
s.push(v[i]);
}
}
}
单调队列
单调队列:队列中数据从队头到队尾具有单调性。