Problem Description

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

Input

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

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

Output

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

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

Example Input

2
4 12 20 15 18
5 20 15 25 30 6

Example Output

12-->20
20-->-11
5-->18
18-->-1
20-->25
15-->25
25-->30
30-->-1
6-->-1

思路：看别人的博客得到的启发，对于每组数据，从后往前遍历。

#include<bits/stdc++.h> using namespace std; struct list { int num; int next; } l[100000]; int main() { int t, n, i; scanf("%d", &t); while(t--) { stack<int>s; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &l[i].num); } for(i--; i >= 0; i--) { if(s.empty())//当栈空时入栈，没有下一较大值 { s.push(l[i].num); l[i].next = -1; } else if(s.top() <= l[i].num)//大于栈顶元素时 { while(s.top() <= l[i].num) { s.pop(); if(s.empty()) { break; } } if(s.empty()) { s.push(l[i].num); l[i].next = -1; } else { l[i].next = s.top(); s.push(l[i].num); } } else if(s.top() > l[i].num)//小于栈顶元素时 { l[i].next = s.top(); s.push(l[i].num); } } for(i++; i<n; i++) { printf("%d-->%d\n", l[i].num, l[i].next); } cout<<endl; } return 0; }