數(shù)據(jù)結(jié)構(gòu)實驗之棧與隊列五：下一較大值（一）

Time Limit:?1000MS?Memory Limit:?65536KB Submit?Statistic?Discuss

Problem Description

對于包含n（1<=n<=1000）個整數(shù)的序列，對于序列中的每一元素，在序列中查找其位置之后第一個大于它的值，如果找到，輸出所找到的值，否則，輸出-1。

Input

?輸入有多組，第一行輸入t（1<=t<=10），表示輸入的組數(shù)；

以后是 t 組輸入：每組先輸入n，表示本組序列的元素個數(shù)，之后依次輸入本組的n個元素。

Output

?輸出有多組，每組之間輸出一個空行（最后一組之后沒有）；

每組輸出按照本序列元素的順序，依次逐行輸出當(dāng)前元素及其查找結(jié)果，兩者之間以-->間隔。

Example Input

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

Example Output

12-->20 20-->-1 15-->18 18-->-120-->25 15-->25 25-->30 30-->-1 6-->-1

Hint

?本題的數(shù)據(jù)量小、限時要求低，可以不用棧來完成。

這道題在開始輸入的時候就進行對數(shù)據(jù)進行處理，當(dāng)輸入每一組數(shù)據(jù)時，當(dāng)棧為空時直接把該數(shù)據(jù)進棧，輸入數(shù)據(jù)時不為空，則進行和棧中的數(shù)據(jù)進行比較....代碼中有詳解

#include <bits/stdc++.h> using namespace std;//用來聲明s棧struct sqstack {int num;//用于記錄輸入的每一組數(shù)據(jù)的大小，從而好與后面數(shù)據(jù)進行比較大小int id,next;//id是為了記錄輸入的這個數(shù)據(jù)是這組數(shù)據(jù)的第幾個，從而便于對a數(shù)組中的next的值進行賦值時找到是數(shù)組中在那個位置上（id位置）//next是用來存儲比num數(shù)值大的那一個數(shù) }; int compear() {sqstack a[1000],p,t;//a數(shù)組到最后是用來進行輸出的對象stack<struct sqstack>s;//s棧int n;scanf("%d",&n);for(int i=0;i<n;++i){cin>>a[i].num;a[i].id=i;a[i].next=-1;//后面會對其進行更改值，代表比他大的第一個值，如果沒有改變說明這組數(shù)據(jù)中沒有比他大的p=a[i];if(s.empty())//遇到空時直接對其進行進棧s.push(p);else{while(!s.empty())//不為空時，同時如果棧中有多個數(shù)據(jù)時會進行循環(huán)，直到為空或者找不到比這個數(shù)值大的{t=s.top();//棧頂元素 if(p.num>t.num){a[t.id].next=p.num;//t.id代表棧頂元素在這組數(shù)據(jù)的位置，同時也代表在a數(shù)組中代表的位置，在此把比他大的值存入到next中，s.pop();//已經(jīng)為a[i-1]找到了第一個比他大的值，所以出棧就行啦，}elsebreak;//如果找不到比t.num大的值得話，最終就會循環(huán)}s.push(p);//a[i]不比a[i-1]大的話就結(jié)束，再把a[i]進棧}}for(int i=0;i<n;++i)printf("%d-->%d\n",a[i].num,a[i].next);return 0; } int main() {int t;scanf("%d",&t);while(t--){compear();if(t)printf("\n");} }

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的sdut-3332 数据结构实验之栈与队列五：下一较大值（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。