题目链接：A Equivalent Prefixes
解题思路
单调栈
我们可以利用单调栈对输入的两个数组进行一下操作：找到比当前数字小的元素，将找到的元素的下标储存起来；
比较两个数组，如果有不一样的，则记录答案，break；
代码如下
1 #include<iostream> 2 using namespace std; 3 const int N = 100000 + 10; 4 struct node{ 5 int inx, val; 6 }st[N]; 7 int n; 8 int a[N], b[N], r1[N], r2[N]; 9 void change(int* temp, int* ans){ 10 int top = 0; 11 st[0] = {0, 0}; 12 for(int i = 1; i <= n; i++){ 13 while(top && st[top].val >= temp[i]) --top; 14 ans[i] = st[top].inx; 15 st[++top] = node{i, temp[i]}; 16 } 17 } 18 int main(){ 19 while(~scanf("%d", &n)){ 20 int ans = n; 21 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 22 for(int i = 1; i <= n; i++) scanf("%d", &b[i]); 23 change(a, r1); change(b, r2); 24 for(int i = 1; i <= n; i++){ 25 if(r1[i] != r2[i]){ 26 ans = i - 1; 27 break; 28 } 29 } 30 printf("%d ", ans); 31 } 32 return 0; 33 }