题目链接：P6510 (opens new window)

思路:

首先将题意转化，对于给定序列，求出最长的连续子序列，满足左端点 A 是子序列的最小值，右端点 B 是子序列最大值，同时左端点与右端点不同，子序列中间的数字也不能与端点相同。

考虑枚举 B，确定 A。

对于每一个 B，显然 A 一定在 B 左边第一个大于等于右端点值的右边，否则从 A 到 B 中一定有一个数字大于等于 B，显然不满足题意，因此我们可以用单调栈 lmax 维护每个下标 i 左边第一个大于等于 h[i] 的值的下标，我们令这个下标为 x。

另外序列中的每个值一定小于右端点的值，所以我们可以再用一个单调栈 lmin 维护每个下标 i 左边第一个小于 h[i]的值的下标，此时单调栈的中所有元素都一定小于右端点的值。我们可以通过二分，来找到第一个大于 x 的下标。

Code:

#include <bits/stdc++.h>

using i64 = long long;

int main() {	
	std::ios::sync_with_stdio(0); 
	std::cin.tie(0);

	int n;
	std::cin >> n;
	std::vector<int> h(n);
	std::vector<int> lmin, lmax;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		std::cin >> h[i];
		while (!lmin.empty() && h[lmin.back()] >= h[i]) 
			lmin.pop_back();
		while (!lmax.empty() && h[lmax.back()] < h[i])
			lmax.pop_back();

		int k = (lmax.empty()) ? 0 : std::upper_bound(lmin.begin(), lmin.end(), lmax.back()) - lmin.begin();
		if (k != lmin.size()) {
			ans = std::max(ans, i - lmin[k] + 1);
		}
		lmin.emplace_back(i);
		lmax.emplace_back(i);
	}
	
	std::cout << ans << "\n";

	return 0;
}	

// Make sure to add code blocks to your code group

PS

1. 之所以单调栈 lmin 不能直接全部作为子序列，是因为此时 lmin 中的每个下标未必连续，中间空着的数字是被弹出去的数字，被弹出去的数字无法保证满足条件。
2. 如果 lmax 为空，则说明此时不存在大于等于 h[i] 的数字，故直接此时单调栈 lmin 所有数字都可以作为子序列的一部分。
3. 这里用的是 STL 实现单调栈，也可以用数组来模拟单调栈。