[题目解析]乐乐的数字

乐乐的数字（allm）

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

乐乐做完数学作业，突发奇想定义了一种新的数：乐乐数。乐乐把n个数排成一行，一个数的“乐乐数”是指：在这个数的左边且比它小的数中最靠近它（即最靠右）的那个数。依次给出这n个数，请求出所有这n个数相对应的“乐乐数”。

输入

第一行是一个正整数n，表示一共有多少个数。 第二行有n个用空格隔开的正整数，它们从左至右给出了数列中的n个数。这些数保证小于2^31。

输出

输出一行用空格隔开的n个数。 这些数对应于输入数据中的数的“乐乐数”。如果输入中某个数没有“乐乐数”（即它左边的数都不比它小），请输出0。

样例输入

样例1

7 3 1 2 7 6 7 4

样例2

5 5 6 3 10 9

样例输出

样例1

0 0 1 2 2 6 2

样例2

0 5 0 3 3

数据范围限制

对于80%的数据，n≦10000； 对于100%的数据，n≦200000。

思路：

此题我们需要先看看这个数据范围，可以看到这个数据范围非常大，所以不能采用两重循环暴力求解法，否则会超时，那要怎么办呢？这时我们就需要考虑新的算法，我们可以牺牲空间减少时间，只要再加一个数组就可以了。这个数组我们就命名为B数组，这个数组主要是拿来储存前一个比他小的数。接着就是1~N的循环了，我们为了减少时间，这里不能直接两重循环，而是可以利用判断+while来解决。进入第一层循环，假如A[i-1]>A[i]的话，我们就需要更新一下内容了，B[i]需要赋值为A[i-1]，而我们的NEXT[i]=i-1。但如果不成立的话变量NXT赋值为NEXT[i-1]，然后就是while循环，循环的条件就是NXT不为零并且A[NXT]>=A[i]，循环内容就是NXT=NEXT[NXT]，这个循环主要的功能就是不停的搜索数字了。

以上为主要的内容解释，接下来上代码👇👇👇

#include<bits/stdc++.h> using namespace std; int t[200001],a[200001],ans[200001]; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ if(!(a[i-1]<a[i])){ int temp=t[i-1]; while(temp!=0&&a[temp]>=a[i]){ temp=t[temp]; } ans[i]=a[temp]; t[i]=temp; } else{ ans[i]=a[i-1]; t[i]=i-1; } } for(int i=1;i<=n;i++){ cout<<ans[i]<<" "; } return 0; }

结合代码和思路应该是能够看懂并理解的，如果还有不懂请在下方留言，我会尽快解答哦（づ￣3￣）づ╭❤～更多题目解析请看我的个人主页