数据结构实验之栈五：下一较大值（一）

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

Problem Description

对于包含n（1<=n<=1000）个整数的序列，对于序列中的每一元素，在序列中查找其位置之后第一个大于它的值，如果找到，输出所找到的值，否则，输出-1。

Input

 输入有多组，第一行输入t（1<=t<=10），表示输入的组数；

以后是 t 组输入：每组先输入n，表示本组序列的元素个数，之后依次输入本组的n个元素。

Output

 输出有多组，每组之间输出一个空行（最后一组之后没有）；

每组输出按照本序列元素的顺序，依次逐行输出当前元素及其查找结果，两者之间以-->间隔。

Example Input

2

4 12 2015 18

5 20 1525 30 6

Example Output

12-->20

20-->-1

15-->18

18-->-1

 

20-->25

15-->25

25-->30

30-->-1

6-->-1

Hint

 本题的数据量小、限时要求低，可以不用栈来完成。

Author

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<stack>
#define N 100100
using namespace std;
struct node
{
    int num,next,data;

};
struct node a[N];




int main()
{
   int t;
   scanf("%d",&t);
   stack<struct node>p;
   for(int i=1;i<=t;i++)
   {

       if(i>1)printf("\n");
       while(!p.empty())
       {
          p.pop();
       }
       int n;
       scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        scanf("%d",&a[j].data);
        a[j].num = j;
        a[j] .next = -1;
        if(p.empty())
        {
           p.push(a[j]);
        }
        else
        {

            while(!p.empty())
            {
                struct node b;
                b = p.top();
                if(b.data<a[j].data)
                {
                    a[b.num].next = a[j].data;
                    p.pop();
                }
                else
                break;



            }
            p.push(a[j]);
        }

    }
    for(int i=1;i<=n;i++)
    {
      printf("%d-->%d\n",a[i].data,a[i].next);

    }







}








return 0;
}




/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 156KB
Submit time: 2017-01-13 15:14:21
****************************************************/