数据结构实验之栈六：下一较大值（二） 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
本题数据量大、限时要求高，须借助栈来完成。
这题之前自己手写了一个栈，简直累死，而且各种出错。后面干脆不自己写了，用c++就是了。
#include <string>#include <stdio.h>#include <stack>using namespace std;typedef struct node{ int num; int id; int next;}node;node a[100010];int main(){ stack<node> damn_stack; int t,n; int i,j,k; scanf("%d",&t); while(t--){ while(!damn_stack.empty())//这里很重要，每次输入一组就要将栈清空 damn_stack.pop(); scanf("%d",&n); for(i=0; i<n; i++){ scanf("%d",&a[i].num); a[i].id = i;//结构体中的id是用来帮助存储比他大的数 a[i].next = -1; if(damn_stack.empty()) damn_stack.push(a[i]); else{ while(!damn_stack.empty()){ node b = damn_stack.top(); if(b.num<a[i].num){ a[b.id].next = a[i].num;//比如先输入的是12 20，那么栈顶就是12，12小于20.同时我们又有12的id，这样就可以让12的next变为20了 damn_stack.pop(); } else break; } damn_stack.push(a[i]); } } for(i=0; i<n; i++) printf("%d-->%d/n",a[i].num,a[i].next); if(t>0) printf("/n"); } return 0;}新闻热点
疑难解答
