题目链接：https://ac.nowcoder.com/acm/contest/881/A
题意：求最大的p，满足[1, p] 任何区间的最小值的下标都相等
题解：假设前面的都符合了，在判断到第i个时，判断前面第一个比a[i], b[i] 小的位置k1, k2是否相同，因为在这个范围内，是a[i]和b[i]小，k1 k2 往前就是已经符合好的了
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int n; stack<pair<int, int> > s1, s2; int main() { while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) scanf("%d", &b[i]); while(!s1.empty()) s1.pop(); while(!s2.empty()) s2.pop(); s1.push(make_pair(0, 0) ); s2.push(make_pair(0, 0) ); int ans = 0; for(int i = 1; i <= n; i++) { while(!s1.empty() && s1.top().first > a[i]) { s1.pop(); } while(!s2.empty() && s2.top().first > b[i]) { s2.pop(); } if(s1.top().second == s2.top().second) { ans = i; } else { break; } s1.push(make_pair(a[i], i)); s2.push(make_pair(b[i], i)); } printf("%d\n", ans); } return 0; }
