单调栈


单调栈

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;
}

原创文章,作者:端木书台,如若转载,请注明出处:https://blog.ytso.com/274226.html

(0)
上一篇 2022年7月14日
下一篇 2022年7月14日

相关推荐

发表回复

登录后才能评论