题目大意

给定两个长度为n的数组，求最大的p，使得1到p以内的所有子区间的对应的最小值的位置相同。
原题目链接https://ac.nowcoder.com/acm/contest/881/A

思路：

首先遍历两个数组，记录每个数组元素左边第一个小于当前数组元素值的位置pos[i]。
再从左到右遍历一遍两个pos数组，记录下第一个posA[i]和posB[i]结果不同的地方，该位置前一个位置就是答案。

思路证明：

对于当前元素的位置i，我们记录的其左边第一个小于当前元素值的位置pos，那么对于（pos,i）,(pos+1,i）… (i,i)是符合题目条件的。
如果pos左侧的值都比pos处的值要大，那么显而易见，（1,i）,（2,i）,…,(pos-1,i)也是符合题意的。
如果pos左侧的值有的比pos处的值小，那么从左往右数，第一个比pos小的值的位置pos2，(pos2,pos1),(pos2+1),…,(pos,pos)是符合题意的，再从pos2开始考虑，用类似递归的思想，很容易明白，（1,i）,（2,i）,…,(pos-1,i)都是符合题意的。
这是右端点是i的情况，但是因为i从左向右遍历，所以之前的所有区间其实都已经检测过了。
AC代码如下

#include <iostream>
#include <stack>
using namespace std;
int a[100005],b[100005],posA[100005],posB[100005];//定义位置数组posA，posB 
int main(){
	int n;
	while(cin>>n){
	    //作为栈底元素用于收割 
		a[0]=-1,b[0]=-1;
		//输入 
		for(int i=1;i<=n;i++)
		    cin>>a[i];
		for(int i=1;i<=n;i++)
		    cin>>b[i];
		stack <int> sta,stb;
		sta.push(0),stb.push(0);
		//记录每个数组元素左边第一个小于当前数组元素值的位置pos[i]
		for(int i=1;i<=n;i++){
			while(a[sta.top()]>a[i])
			sta.pop();
			posA[i]=sta.top();
			sta.push(i);
			while(b[stb.top()]>b[i])
			stb.pop();
			posB[i]=stb.top();
			stb.push(i);
		}
		//再从左到右遍历一遍两个pos数组，记录下第一个posA[i]和posB[i]结果不同的地方 
		int p=1;
		for(int i=1;i<=n;i++){
			if(posA[i]==posB[i])
			    p=i;
			else
			break;    
		}
		cout<<p<<endl;
	}
	return 0;
}

另外一种比较暴力的思路：

{1，2，3}的子区间对于{1，2，3，4}的子区间而言只多了（3，4），（2，3，4），（1，2，3，4）这几个区间，也就是（1，i），（2，i），（3，i）所以按照这个思路，遍历数组进行判断就可以。
AC代码如下

#include <iostream>
using namespace std;
int a[100010],b[100010];
int main(){
    int n,p,i,ans,pos;
    while(cin>>n){
        ans=n;
        for(i=1;i<=n;i++)
        cin>>a[i];
        for(i=1;i<=n;i++)
        cin>>b[i];
        for(p=1;p<=n;p++){
            pos=1;
            for(i=p-1;i;i--){
            if((a[p]>a[i]&&b[p]<b[i])||(b[p]>b[i])&&a[p]<a[i]){
                pos=0;
                break;
            }
            if((a[p]>a[i])&&(b[p]>b[i])){
                break;
            }            
            }
            if(!pos){
            ans=p-1;
            break; 
            }
             
        }
        cout<<ans<<endl;   
    }
    return 0;
}

参考博客：
http://www.manongjc.com/detail/8-szmegimpjimowzk.html