首先发出题目链接： 链接：https://ac.nowcoder.com/acm/contest/881/A 来源：牛客网 涉及：单调栈
点击这里回到2019牛客暑期多校训练营解题—目录贴
题目如下： 迟到的总结讲解
首先我们可以把每个样例两组点钟所有的点按照顺序画在两个坐标系中，连点成折线图 比如{3 1 5 2 4}这组点的折线图为
分析可得，如果要让两个值的RMQ值，我们需要让两连个折线图单调性一致。
我们知道，在折线图中无非有下列四种情况： 递减、递增、先减再增、先增再减
其他情况都可以分解为这四种基本情况
考虑第一种情况：递减 如图所示，如果在两组点的折线图的第 l l l个点到第 r r r个点内是递减趋势，那么在这一片区域中，最小值的下标都是 r r r，满足条件。
考虑第二种情况：递增 如图所示，如果在两组点的折线图的第 l l l个点到第 r r r个点内是递增趋势，那么在这一片区域中，最小值的下标都是 l l l，满足条件。
考虑第三种情况：先减再增 如图所示，如果在两组点的折线图的第 l l l个点到第 r r r个点内是先减再增趋势，那么在这一片区域中，最小值的下标都是 m m m，满足条件。
考虑第四种情况：先增再减 如图所示，如果在两组点的折线图的第 l l l个点到第 r r r个点内是先增再减趋势，那么就要注意，这片区域最小元素的下标可能是 l l l，也可能是 r r r，不一定满足条件。
我们可以用两个单调栈来分别维护两个折线图的壳，如果在第 l l l到第 r r r个点之间的趋势完全不一样，那么两个单调栈栈顶的出栈和入栈顺序就会不一样，最后单调栈的元素个数就会发生改变。
如果对应单调性一样，在折线图某个区域内的点有两种情况： 1.一种除先增后减以外的趋势，那么单调栈栈顶出栈入栈顺序仍然一样 2.还有一种就是先增后减的趋势，如果两个折线图在此区域内第 l l l个元素都比第 r r r个元素大（或者小），最后单调栈的出栈入栈顺序仍然一样；否则出栈入栈顺序不同，导致单调栈内元素个数不同。
可以弄两个单调递增的单调栈分别维护两个折线图，可以每考虑两个数组对应位置的两个元素是否入栈或出栈，每考虑一个值然后就判断两个栈内元素个数是否相同，直到不相同，说明找到了P值（最后考虑的点的上一个点的下标就是P指）。
代码如下：
#include <algorithm> #include <iostream> #include <stack> using namespace std; const int N = 1e5+5; stack<int> Ma;//两个栈 stack<int> Mb; int a[N];//两个数组 int b[N]; int n; void initMa(){ while(!Ma.empty()) Ma.pop(); } void initMb(){ while(!Mb.empty()) Mb.pop(); } int main(){ while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<n;i++) scanf("%d",b+i); //刚开始清空栈 if(!Ma.empty()) initMa(); if(!Mb.empty()) initMb(); //先把每个数组第一个值丢到对应的栈里面 Ma.push(a[0]); Mb.push(b[0]); int k = 1; for(int i=1;i<n;i++){ while(1){//判断a数组第一个值是否入栈（或出栈） if(Ma.empty() || Ma.top() < a[i]){ Ma.push(a[i]); break; } else Ma.pop(); } while(1){//判断b数组第一个值是否入栈（或出栈） if(Mb.empty() || Mb.top() < b[i]){ Mb.push(b[i]); break; } else Mb.pop(); } //结束后，开始比较两个栈元素个数，不相同就结束 if(Ma.size() != Mb.size()) break; k++;//k就是答案，每次循环就加一次 } cout<<k<<endl; } return 0; }