思路与算法

从左到右把当前点当作严格最大右端。递减栈给出之前最后一个高度≥当前值的位置barrier，左端必须在其后。另维护严格递增高度的候选左端栈；当前高度不大于栈尾时，该尾部作为未来严格最小左端已失效，弹出。对剩余候选下标二分找第一个大于barrier的位置，更新最长长度，然后加入当前点。

正确性说明

递减栈确定任一区间以当前点为严格最大值的充要左边界。候选最小栈中的每个位置到当前之前都没有更小或相等值；被弹出的位置永远不能再成为跨过当前点的严格最小。于是剩余下标中大于barrier的最早一个，恰给当前右端的最长合法区间。

复杂度

两个栈每个下标各进出一次O(N)，每次二分O(logN)，总O(NlogN)时间；输入和栈初始化O(N)，空间O(N)。

易错点

相等值不允许作为内部与端点同高：最小栈用>=弹出，最大栈只用<弹出。答案初始0，当前点入栈之前才查询，避免长度1。高度可到2^32-1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<unsigned long long> a(n);
    for (auto &x : a)
        cin >> x;
    vector<int> mn, mx;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        while (!mx.empty() && a[mx.back()] < a[i])
            mx.pop_back();
        int barrier = mx.empty() ? -1 : mx.back();
        while (!mn.empty() && a[mn.back()] >= a[i])
            mn.pop_back();
        auto it = upper_bound(mn.begin(), mn.end(), barrier);
        if (it != mn.end())
            ans = max(ans, i - *it + 1);
        mn.push_back(i);
        mx.push_back(i);
    }
    cout << ans << '\n';
}