如果一个人比你强比你年轻，那么你就废了!
-------单调队列
刚学完单调栈，单调队列感觉自己就算刷蓝题都没问题了，然后就被绿题打脸了(bushu
一开始看到这题迷迷糊糊就写了一个单调栈和一个单调队列组合起来的抽象代码。
底层逻辑是这样的:只要最大值的位置在最小值的右边，那么这个区间就是合法的。并且细心的打补丁把ans=1的情况算为0(读题了，但又没完全读题)
\(70pts~code:\)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long n,a[100010],ans;
struct ubt{long long v,dis;};
deque <ubt> qmax,qmin;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){while((qmax.size()>=1)&&(qmin.size()>=1)&&qmax.front().dis<qmin.front().dis)qmax.pop_front();while((qmax.size()>=1)&&qmax.back().v<=a[i])qmax.pop_back();while((qmin.size()>=1)&&qmin.back().v>=a[i])qmin.pop_back();qmax.push_back((ubt){a[i],i});qmin.push_back((ubt){a[i],i});ans=max(qmax.front().dis-qmin.front().dis+1,ans);}if(ans==1)ans=0;cout<<ans;return 0;
}
后来发现在面对
6
1 9 3 7 6 9
这种样例是错的，又加了补丁(补丁神)
while(qmin.size()&&qmax.size()&&a[i]==qmax.back().v){while(qmin.front().dis<=qmax.back().dis)qmin.pop_front();qmax.pop_back();}}
依旧\(70pts\)
正解
终于在查找题解，进行读天书环节后终于明白了
思路
对于一个合法区间，对于右端点i，在相较于右端点位置靠前的所有大于等于右端点的端点之后的位置即是右端点i的最优左端点
(原谅我语文不好)
所以我们只需要枚举右端点i，并且用单调栈记录我们的所有比i大的端点，以及所有可能的左端点(注意只有前面有比它大的端点，它才能成为左端点，因为比它大的点，将它于最小的点隔开了)
\(压行极简风~100pts\)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],mx[100010],mi[100010],xs,is,ans;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){while(xs&&a[mx[xs]]>=a[i])xs--;while(is&&a[mi[is]]<a[i])is--;int u=upper_bound(mx+1,mx+1+xs,mi[is])-mx;if(u!=xs+1)ans=max(ans,i-mx[u]+1);xs++;mx[xs]=i;is++;mi[is]=i;}cout<<ans;return 0;
}1.每次记录比a[i]大的端点
2.用二分查找的方式找到距a[i]最近的大于等于它的端点(因为mi[is]肯定是第二大端点，如果不是那么在代码第10行就被淘汰了，并且如果二分查找找到的数肯定大于他，如果大于它就相当于大于等于a[i],因为它是第二大端点)
3.最后相减取max，并把i放进单调栈了，因为后面的遍历要用
ending
\(update-2026-2-6\)
更改病字和认知上的错误