单调栈

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