[数据结构与算法]数据结构——单调栈

题目描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 ?1。

输入格式
第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 ?1。

数据范围
1≤N≤10⁵
1≤数列中元素≤10⁹
输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

暴力解法（二重循环）(当数据量很大时会超时)

import java.util.*;

public class Main{
    static int N = 100010;
    public static void main(String[] args){
        int n;
        int[] a = new int[N];
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            int j;
            for(j=i-1;j>=0;j--){
                if(a[j]<a[i]){
                    System.out.print(a[j]+" ");
                    break;
                }
            }
            if(j==-1)System.out.print("-1 ");
        }
    }
}

单调栈解法

分析：
当a[i] 的左边有两个数a[x]，a[y]同时满足a[x]>=a[y]且x<y;那么对于a[i]以及a[i]后面的数来说，这个a[x]是无效的可以剔除掉，

import java.util.*;

public class Main{
    static int N = 100010;
    public static void main(String[] args){
        int[] stk = new int[N];
        int tt=-1;
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        for(int i=0;i<n;i++){
            int x = sc.nextInt();
            //栈里有数，且栈顶数比x大，那么就剔除栈顶数，直到栈顶数小于x,
            while(tt>=0 && stk[tt]>=x) tt--;
            //那么此时的栈顶数就是我们要找的数
            if(tt>=0)System.out.print(stk[tt]+" ");
            //如果栈里所有的数都被剔除了，就说明当前的x是最小的，它前面没有比他小的数
            else System.out.print("-1 ");
            //将x加入到栈中
            stk[++tt] = x;
        }
    }
}