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

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

Time Limit: 150MS Memory Limit: 8000KB Submit  Statistic

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

思路：我们需要仔细想一想我们不需要的东西，因为我们找的是下一个较大值，所以我们用栈来存储一个递增序列即可，因为出现递减是我们所不需要的。

要想完成这个第一个较大值的寻找，那么我们应当倒着来。

从后面开始，

1.如果栈为空，说明下一较大值不存在。把当前值压入栈

2.如果栈中找不到比当前值大的，说明下一较大值不存在。找的时候应当是不断弹出栈的，因为比当前值小的元素是我们所不需要的。

3.如果找到了比当前值大的，说明下一较大值就是它，然后把当前值压入栈。

#include <iostream> #include <bits/stdc++.h> using namespace std; const int MAXN=100000+5; int num[MAXN]; int ans[MAXN]; int sta[MAXN]; int main() { int t; int n,i; while(~scanf("%d",&t)) { while(t--) { scanf("%d",&n); for(i=0;i<n;++i)scanf("%d",&num[i]); int top=0; ans[n-1]=-1;//第一个自然是-1 sta[top++]=num[n-1];//压入栈 for(i=n-2;i>=0;--i) { if(num[i]<sta[top-1])//如果栈顶满足条件 { ans[i]=sta[top-1];//下一较大值就是栈顶元素 sta[top++]=num[i];//入栈 } else { while(num[i]>=sta[top-1]&&top)top--;//否则一直找 if(!top)ans[i]=-1;//栈空表示没找到 else ans[i]=sta[top-1];//找到了 sta[top++]=num[i];//当前元素入栈 } } for(i=0;i<n;++i)printf("%d-->%d\n",num[i],ans[i]); if(t)printf("\n"); } } return 0; } /*************************************************** Result: Accepted Take time: 92ms Take Memory: 936KB Submit time: 2016-09-19 11:57:34 ****************************************************/