数据结构实验之栈与队列:下一较大值

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

29

题一:处理小于等于1000的数据

数据结构实验之栈与队列五:下一较大值(一)
Problem Description
对于包含n(1<=n<=1000)个整数的序列,对于序列中的每一元素,在序列中查找其位置之后第一个大于它的值,如果找到,输出所找到的值,否则,输出-1。

Input
输入有多组,第一行输入t(1<=t<=10),表示输入的组数;

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

Output
输出有多组,每组之间输出一个空行(最后一组之后没有);

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

Sample Input
2
4 12 20 15 18
5 20 15 25 30 6 
Sample Output
12-->20
20-->-1
15-->18
18-->-120-->25
15-->25
25-->30
30-->-1
6-->-1

Hint
本题的数据量小、限时要求低,可以不用栈来完成。

使用数组解决:

#include 
using namespace std;
int main()
{int t;cin >> t;for (int i = 0; i < t; i++){int array[1000];int n;cin >> n;for (int j = 0; j < n; j++){cin >> array[j];}for (int j = 0; j < n; j++){int temp = -1;cout << array[j] << "-->" ;for (int k = j+1; k < n; k++){if (array[k] > array[j]){temp = array[k];break;}}cout << temp;cout << endl;}if (i != t-1)cout << endl;}return 0;
}

小于等于100000的数据

数据结构实验之栈与队列六:下一较大值(二)

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

Input
输入有多组,第一行输入t(1<=t<=10),表示输入的组数;

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

Output
输出有多组,每组之间输出一个空行(最后一组之后没有);

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

Sample Input
2
4 12 20 15 18
5 20 15 25 30 6
Sample Output
12–>20
20–>-1
15–>18
18–>-1

20–>25
15–>25
25–>30
30–>-1
6–>-1
Hint
本题数据量大、限时要求高,须借助栈来完成。

从左向右扫描


#include 
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;int array[100000];int larger[100000];int stack[100000];int *top = stack;for (int j = 0; j < n; j++){cin >> array[j];larger[j] = -1;}for (int j = 0; j < n; j++){//当前元素e比栈顶元素大的时候,将栈顶元素出栈,并在larger数组中找到对应位置赋值为ewhile (top != stack && *(array[j] > top - 1)){int i = j - 1;while (i >= 0 && larger[i] != -1){i--;}top--;larger[i] = array[j];}//栈为空,直接入栈if (top == stack)*(top++) = array[j];//当前元素e比栈顶元素小,直接入栈else if (array[j] < *(top - 1)){*(top++) = array[j];}}for (int j = 0; j < n; j++){cout << array[j] << "-->" << larger[j] << endl;}if (t)cout << endl;}return 0;
}

这是从左向右遍历数组,这里得到在数组中位置为i的数组元素e,无法直接得到是否有较大值,还需要之后的数组元素大小来判断,后面元素大于e,e出栈,否则一直等待。这样还是无法AC,超时。

从右向左扫描

下面换一下方向,从右向左遍历,我们来看看情况如何。
我们知道对于任意一组数据,最右端的元素一定没有较大值,一定是它对应的较大值一定是-1;

  1. 如果是最右端元素直接入栈s;
  2. 否则,当前元素e和栈顶元素比较
    a.如果比栈顶元素小,那么该栈顶元素就是e的较大值,e再入栈
    b.如果比栈顶元素大,栈顶元素出栈,继续和下一个栈顶元素比较,直到找到比e大的栈顶元素or栈空(栈空的话较大值是-1,否则就是那个比e大的栈顶元素),e再入栈
#include 
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;int array[100000];int larger[100000];int stack[100000];int *top = stack;for (int j = 0; j < n; j++){cin >> array[j];}for (int j = n-1; j >= 0; j--){while (top != stack && array[j] >= *(top - 1)){top--;}if (top == stack){larger[j] = -1;*(top++) = array[j];}else if (array[j] < *(top - 1)){larger[j] = *(top - 1);*(top++) = array[j];}}for (int j = 0; j < n; j++){cout << array[j] << "-->" << larger[j] << endl;}if (t)cout << endl;}return 0;
}