think：1、栈结合动态规划，两种思想的一种动态结合。 2、hint:数据量大、限时要求高
数据结构实验之栈六：下一较大值（二） Time Limit: 150MS Memory Limit: 8000KB
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–>-1 15–>18 18–>-1
20–>25 15–>25 25–>30 30–>-1 6–>-1
Hint 本题数据量大、限时要求高，须借助栈来完成。 Author
以下为accepted代码
#include <stdio.h> #include <string.h> #define MAXN 100004 struct node { int date; int ans; }a[MAXN]; struct node1 { int date; int id; }stacks[MAXN]; int top; int main() { int T, n, i; scanf("%d", &T); while(T--) { top = -1; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &a[i].date); a[i].ans = -1; if(top == -1) { top++; stacks[top].date = a[i].date; stacks[top].id = i; } else { while(top != -1) { if(stacks[top].date < a[i].date) { a[stacks[top].id].ans = a[i].date; top--; } else { top++; stacks[top].date = a[i].date; stacks[top].id = i; break; } } if(top == -1) { top++; stacks[top].date = a[i].date; stacks[top].id = i; } } } for(i = 0; i < n; i++) printf("%d-->%d\n", a[i].date, a[i].ans); if(T != 0) printf("\n"); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 100ms Take Memory: 1672KB Submit time: 2017-02-02 09:43:41 ****************************************************/