在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，
第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j > i)。
请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。
小朋友人数范围是 [0, 40000]。
//暴力解法
#include<stdio.h>
int main(){
int height[40001]={
0};
int friend[40001]={
0};
int n=0;
printf("请输入孩子个数：");
scanf("%d",&n);
printf("请输入孩子身高：");//从左到右是从头到尾
for(int i=1;i<=n;i++){
scanf("%d",&height[i]);
}
for(int i=n;i>1;i--){
//从尾部向前找第一个比自己高的
int j=i-1; //从前一个人开始找
while(height[i]>=height[j]&&j>0)
j--;
if(j==0)
friend[i]=0; //表示没朋友
else
friend[i]=j; //i号位置的朋友在j号位置
}
for(int i=1;i<=n;i++)
printf("%d ",friend[i]);
return 0;
}
使用栈来避免重复的比较，单调栈的应用
1.从第一个小朋友身高开始扫描，第一个小朋友a直接压如栈中，扫描下一个小朋友b的身高，假设b后边的小朋友是c
2.若b的身高比a高，就让a出栈，理由如下：
①a不会是b的朋友
②在b后边的小朋友的朋友一定不会是a，b的朋友属性优于a，因b离后边小朋友更近且更高
3.若a的身高比b的高，则将a保留在栈中，并让b入栈，理由如下：
①a一定是b的朋友，但是b后边的小朋友的朋友，可能是a也可能是b，因a虽离得远，但是a比b高
4.栈中相邻元素中，前一个一定是后一个的朋友，朋友才会在栈中相遇相邻
