题目描述 Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r)for all 1≤l≤r≤mwhere RMQ(w,l,r)RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wr. Since the array contains distinct elements, the definition of minimum is unambiguous. Bobo has two arrays a and b each with n distinct elements. Find the maximum number p≤np≤n where {a1,a2,…,ap}and {b1,b2,…,bp} are equivalent.
题意：
使输入中的两个数组在 前P个位置（中间任意区间中 的最小值对应的索引位置相同），然后求 P
解题思路：
单调栈维护两个数组内元素单调递增，当栈内元素 的个数不相同时，退出循环
#include <cstdio> #include <queue> #include <cstring> #include <stack> #include <iostream> #include <cmath> using namespace std; stack<int> sta1,sta2; int main(){ int n; while(cin >> n){ int a[100005],b[100005]; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ cin >> b[i]; } int k = 1; // 清空两个栈 while(!sta1.empty()){ sta1.pop(); } while(!sta2.empty()){ sta2.pop(); } sta1.push(a[1]); // 放入初始元素 sta2.push(b[1]); while(k < n){ while(!sta1.empty() && sta1.top() > a[k+1]){ sta1.pop(); // 当后一个元素小于栈顶元素时，弹出 } if(sta1.empty() || a[k+1]>sta1.top()){ //此处可以不写判断，因为上面的while判断过 // 写判断条件时，栈为空应写在前面，否则不会有.top(),会溢出 sta1.push(a[k+1]); // 将后一个元素压入栈中 } while(!sta2.empty() && sta2.top() > b[k+1]){ sta2.pop(); } if(sta2.empty() || b[k+1] > sta2.top()){ sta2.push(b[k+1]); } if(sta1.size() != sta2.size()){ break; //长度不相同说明有区间最小值得索引发生变化直接退出 } k++; } cout << k << endl; } return 0; }
