题目描述

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 \(A\) 是最矮的，最右边的 \(B\) 是最高的，且 \(B\) 高于 \(A\) 奶牛。中间如果存在奶牛，则身高不能和 \(A,B\) 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 \(0,2\)，但不会是 \(1\)）。

输入格式

第一行一个正整数 \(N\)，表示奶牛的头数。

接下来 \(N\) 行，每行一个正整数，从上到下表示从左到右奶牛的身高 \(h_i\)。

输出格式

一行一个整数，表示最多奶牛数。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

取第 \(1\) 头到第 \(4\) 头奶牛，满足条件且为最多。

数据范围

对于全部的数据，满足 \(2 \le N \le 10^5\)，\(1 \le h_i <2^{31}\)。

浅浅谈一下

记一个右端点 \(r\)，假设我们维护了 \([1,r]\) 的后缀最大和最小值，这个区间之外的数我们不考虑

\(r\) 为区间最大值，则 \(l\) 必须要大于 \(r\) 的上一个后缀最大值
\(l\) 为区间最小值，那么 \(l\) 为这个前缀的最小值

记 \(r\) 的上一个后缀最大值为 \(p\)，则要找 \(p\) 之后的后缀最小值（当然，越小越好）

二分即可

\(\mathcal{Code}\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 7;

int n, ans;
ll a[MAXN];
vector<int> maxx, minn;//后缀最小值和后缀最大值 


int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	generate (a + 1, a + 1 + n, [](){ll x; cin >> x; return x;});

	maxx.push_back(0), minn.push_back(0);
	for (int r = 1; r <= n; r ++) {//枚举右端点
		while (!maxx.empty() && a[maxx.back()] <= a[r] && maxx.back() != 0) maxx.pop_back();
		while (!minn.empty() && a[minn.back()] >= a[r]) minn.pop_back();
		int l = upper_bound(minn.begin(), minn.end(), maxx.back()) - minn.begin();
		//不存在返回a.end() 
		if (l != minn.end() - minn.begin()) ans = max (ans, r - minn[l] + 1);
		maxx.push_back(r), minn.push_back(r);
	}
	cout << ans << endl;
	return 0; 
}

完结撒花✿✿ヽ(°▽°)ノ✿