单调栈单调队列

单调栈

单调栈：栈中数据从栈底至栈顶具有单调性。要求序列中每个元素都必须要进入一次单调栈。由于单调栈的特性，每个元素可能并不会在遍历序列之后仍然保留在单调栈内。

应用：求解 $NGE / N L E 、 PGE / P L E$ 问题( $Next/Previous\ Greater/Less\ Element$ )。

$G re a t er$ 类问题：构造单调递减栈
$L ess$ 类问题：构造单调递增栈
$P re v i o u s$ 类问题：以即将入栈的元素为视角看栈顶元素，不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)
$N e x t$ 类问题：以栈顶元素为视角看即将入栈元素，允许即将入栈元素与栈顶元素相同

$NGE / N L E$ 问题

$NGE$ :构造单调递减栈，以栈顶元素为视角看即将入栈元素，允许即将入栈元素与栈顶元素相同
$N L E$ :构造单调递增栈，以栈顶元素为视角看即将入栈元素，允许即将入栈元素与栈顶元素相同

//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]);
        }
    }
}

$PGE / P L E$ 问题

$PGE$ :构造单调递减栈，以入栈元素为视角看栈顶元素，不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)
$P L E$ :构造单调递增栈，以入栈元素为视角看栈顶元素，不允许栈顶元素与即将入栈元素相同(入栈前必须将栈中与其相同元素全部岀栈)

//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]);
        }
    }
}