luo2086-----奶牛排队 题解

题目

奶牛排队

题目描述

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

输入

输入 第一行一个数N（2< =N< =100000），表示奶牛的头数。 接下来N个数，每行一个数，从上到下表示从左到右奶牛的身高（1< =身高< =maxlongint）。

输出

输出 一行，表示最多奶牛数。

样例

输入

5
1
2
3
4
1

输出

4

补充

时间限制 2 秒
内存限制 128 MB
来源 luo’s OJ

题解

可以理解为一个大的值，可以把前面比他小的值都吞灭，然后记录吞灭的最小值位置
所以可以构造单调下降队列（栈），表示将每个小递增段并到最后一个高点上
每个高点可以向左找被吞并小段的低点，记录最低点，高点到这个最低点位置为一个答案

#include <bits/stdc++.h>
using namespace std;
int n,a[100010];
int sum;
struct Node{
	int x,y;
}t;
deque<Node> q;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for (int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
		t.x = i;
		t.y = i;
		while(!q.empty() && a[q.back().y] < a[i]){
			if (a[t.x] > a[q.back().x]){
				t.x = q.back().x;
			}
			q.pop_back();
		}
		sum = max(sum,t.y-t.x+1);
		q.push_back(t);
	}
	if (sum == 1){
		sum = 0;
	}
	printf("%d",sum);
	return 0;
}

测评结果 通过
分数 100
耗时 132 MS
内存 3380 KB
语言 C++
代码长度 544 bytes