ACWing 803
给定一个长度为 NN 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1−1。
第一行包含整数 NN,表示数列长度。
第二行包含 NN 个整数,表示整数数列。
共一行,包含 NN 个整数,其中第 ii 个数表示第 ii 个数的左边第一个比它小的数,如果不存在则输出 −1−1。
1≤N≤1051≤N≤105
1≤数列中元素≤1091≤数列中元素≤109
5 3 4 2 7 5
-1 3 -1 2 2
这道题题意很简单,就是为一个元素忘左走最先碰到的比他小的元素。最直观的方式就是用双重循环
/** * 栈 */ #include<bits/stdc++.h> using namespace std; const int N = 100100; int a[N]; int b[N]; int main(){ int n; cin>>n; for(int i =1; i<=n; i++) { cin>>a[i]; } for(int i = 1; i<=n; i++) { for(int j = i-1;j>=1; j--) { if(a[j]<a[i]){ b[i] = a[j]; break; } } } for(int i =1; i<=n; i++){ if(b[i]== 0){ cout<<"-1 "; }else { cout<<b[i]<<" "; } } }
但是这种方法的时间复杂度太大了O(n^2)
怎么优化呢,观察规律,如果一个数他比他的前一个数小,那么再往前搜的时候,是不是他前一个数就不会再出现了,所以我们用到单调栈
所谓单调找就是栈里的元素是有序的,那这道题怎么做呢:
当遍历到ai的时候,那它和栈顶元素比,如果比栈顶元素小,就一直出栈,知道遇到比他小的,然后将其入栈.
代码
/** * 栈 */ #include<bits/stdc++.h> using namespace std; const int N = 10010; int sta[N]; int t; int n; int main() { cin>>n; for(int i = 0; i<n; i++) { int a; cin>>a; while(t && sta[t]>=a)t--; if(t)cout<<sta[t]<<" "; else cout<<-1<<" "; sta[++t] = a; } return 0; }