平淡地用两个单链表解决

解题思路:先说一下我对该题的理解

1. 从一层楼飞到另一层楼时，其中间不能有高处于两楼高之间的，因为有的话应当先飞往该楼再飞下一楼，否则会少飞一个使经过层数不是最大值。以该规则为基础可以使计算新的高度的经过层数为最大值。

2. 选第一个开始飞时，与飞行方向相反的其他楼高度不能大于原选的起飞楼的高度，否则以那一个更高的起飞能使经过层数更高

3. 以第二点可以推出，每个楼要么作为起飞，跳过和经过

4. 若有两个高度的经过层数相同，则将高度低的删除，毕竟越高能经过的肯定大于等于低的。同理，若有两个高度其中高度更高的经过层数还的大于等于高度低的，则删除高度低的。优化算法，节省空间，

5. 从第一点我们可以推出，加入一个新高度时，它的最大经过层数就是链表中高度刚好大于它的楼的层数加一。再从第二和三点推出，在链表中找不到大于它的高度时，它就只能是起飞楼，它的经过层数为它自身，即1。

代码的话，用两个单链表，第一个链表按高度从大到小，同时，经过层数从小到大，链表中储存每个高度对应经过的最大层数。

每当插入一个新的数时，以规则5可以找到该高度应该插在链表的位置和最大经过层数，然后以规则4删掉经过层数和高度均小于新的高度的楼。以此形成循环。

第二个链表为高度从小到大，且经过层数仍然从小到大，因为从高飞到低和从低飞到高没有区别，这样用两个链表就可以不用特意定义一个数组来储存每个楼的高度，直接两个链表同时进行。

（很意外，本以为会报错或超时但是却很出乎我自己的意料地过了，因为没做多少检查，还想再继续优化

并且之前在做兔子集结但是一直结果错了和超时，并且一直找不到哪里错了）
注意事项:

参考代码:

typedef struct node{      //链表定义
	int h;            //高度
	int i;            //经过的楼层数，个人新手习惯用i，可以按习惯改成data
	struct node *next;//下一个指针
}node;
	node frist1,last1,frist2,last2;//定义头链表和尾链表，方便插入和检测
void charu(){
	int h;
	scanf("%d",&h);                         //拿参数
	node *root=(node *)malloc(sizeof(node));//开始整从高到低的第一个链表
	node *a=&frist1;      //定义指针a并指向链表头
	while(a->next->h >=h)a=a->next;//这里是找下一楼的高度刚好大于，这样循环结束时，我们插入的位置就是a指向的楼的下一个
	root->next =a->next ;
	root->h =h;
	root->i =a->i +1;
	a->next =root;                 //将root和上一个相连
	a=root->next;
	while(a->i<=root->i){           //以规则4删节点
		root->next=a->next;
		free(a);
		a=root->next;
	}
	node *reet=(node *)malloc(sizeof(node));//开始整从低到高的第二个链表
	a=&frist2;
	while(a->next->h <=h)a=a->next;//循环条件改了
	reet->next =a->next ;
	reet->h =h;
	reet->i =a->i +1;
	a->next =reet;
	a=reet->next;                 //将a指向root的下一个
	while(a->i<=reet->i){         //如果a即root的下一个的经过层数大于i+1再推出循环
		reet->next=a->next;   //储存root的下一个的下一个在root->next
		free(a);              //将root的下一个删掉
		a=reet->next;         //重新将a指向root的下一个
	}
}
main(){
	int x,n,max;
	last2.h =frist1.h =10000;//找链表插入位置时用的
	frist2.h =last1.h =0;      //找链表插入位置时用的
	frist2.i =frist1.i =0;//链表头的经过层数为0，这样可以使插入起飞楼的经过层数为头链表的0+1达成1
	last2.i =last1.i =100;//链表尾的经过层数设为100，因为题目说最多有99座楼，使插入最多插入链表尾前一个
	scanf("%d",&x);
	for(int i=0;i<x;i++){//大循环
	frist1.next =&last1;//每次循环均要将头链表的下一个指向链表尾
	frist2.next =&last2;
		scanf("%d",&n);
		for(int x=0;x<n;x++) charu();//小循环
		node *a =frist1.next;
		while(a->next->i!=100){//将charu函数里定义的空间给释放顺便拿最大值，注意这里由于循环判定里是用a->next，会使最后会留last上一个
		frist1.next=a->next;//其实这个while是抄charu函数里的while的
		free(a);
		a=frist1.next;//最后留的那一个的值就是最大值,所以要使它不被free ,
	}
	max=a->i ;//将值存在max
	free(a);//清除最后一个
	a =frist2.next;
		while(a->next->i!=100){//第二个链表的清空间和拿最大值
		frist2.next=a->next;
		free(a);
		a=frist2.next;
	}
	if(a->i >max)max=a->i ;
	free(a);//清除最后一个
	printf("%d\n",max);
	}
}