Cogs奶牛排队

奶牛排队

奶牛排队 【题目描述】

奶牛在熊大妈的带领下排成了一条直队。
显然，不同的奶牛身高不一定相同…… 现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，中间如果存在奶牛，则身高不能和A、B奶牛相同。问这样的奶牛最多会有多少头？ 从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是0，2，但不会是1）。 【输入格式】

第一行一个数N (2≤N≤100000)，表示奶牛的头数。 接下来N个数，每行一个数，从上到下表示从左到右奶牛的身高(1≤身高= maxlongint)。 【输出格式】

一行，表示最多奶牛数。

此时，s中的左端单调栈维护 单调栈里存放着一些区间，贮存的信息有 左端点位置pos，左端点的值l，以及当前这个区间的最大值(右端点)max

如果增加了一个节点，那么它可以作为右端点，也可以作为左端点

做为右端点的话，首先原区间的l必须要小于它，不然l就不是最小值了；而左端点合法的区间，它也只能封住max比它小的区间 同时他自己也是一个左端点 所以我们要做这样的操作： 新加入一个点，我都要删除已经不再合法的区间，也就是所有l大于它的区间 然后，这时所有的区间，l必定合法 此时加入一个新的区间，以当前值为左端点的区间 然后试着去更新前面的点的最大值 如果一个点不再能够被更新，那么它后面那个点，就是最靠前的我所能够更新的点，那么在这个区间之后，所有的区间也能够被更新，不过他们都没有意义：因为左端点在这个区间的左端点之后，且右端点相同，那么是一种包含的关系，所以没有必要在存在 当然，代码对区间的把控不太好，以至于无解出来了1，也就是删除啊更新啊的时候大于等于这种去重的操作做得不太好吧…点，都是合法的

#include<iostream>
#include<cstdio>
using namespace std;
int n,say,top,ans;
struct node
{
	int pos,max,l;
}s[100010];
int read() 
{
    int out=0,flag=1;
    char c=getchar();
    while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
    while(c>=48&&c<=57)
    {
        out=out*10+c-48;
        c=getchar();
    }
    return out*flag;
}
int main()
{
	freopen("tahort.in","r",stdin);
	freopen("tahort.out","w",stdout);
	n=read();
	say=read();
	s[++top]=(node){1,say,say};
	for(int i=2;i<=n;++i)
	{
		say=read();
		while(top&&s[top].l>say) top--;
		s[++top]=(node){i,say,say};
		while(top&&s[top].max<=say) top--; 
		s[++top].max=say;
		ans=max(ans,i-s[top].pos+1);
	}
	if(ans==1) ans=0;
	printf("%d",ans);
	return 0;
}