题目描述

给定一个数组，输出每一个元素的左边的第一个比他小的元素。

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

算法1

(单调栈) $O(n)$

思路：
- 首先是让从当前值的从右向左看的第一个比他小的值，说明是先进后出，可以用栈来模拟一下。
- 然后假设当第三个值stk[3]>=当前值i的话，是不是说明从i往后的数都不会用到stk[3],所以它可以删除了
- 所以当遍历数组的时候，每次都判断一下当前值的左边是否有比他大的值，有的话删除，直到找到比他小的然后输出，这样的话每次进入循环都是严格递增的栈，避免了不必要的比较

时间复杂度： $O(n)$

参考文献：y总

Java 代码

BufferedReader

import java.io.*;
/*
单调栈
 */
public class Main {
    static int N = 100010;
    static int[] stk = new int[N];
    static int tt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine().split(" ")[0]);
        String[] str_01 = br.readLine().split(" ");
        for (int i = 0; i < n; i++){
            int x = Integer.parseInt(str_01[i]);
            while (i != 0 && stk[tt] >= x) tt--;// 当不是一个数并且栈顶元素大于插入的值，删除
            if (tt == 0) bw.write(-1 + " ");// 当栈中元素是空的时候输出 -1
            else bw.write(stk[tt] + " ");// 栈顶元素就是左侧第一个最小的

            stk[++tt] = x;// 把新的元素插入到栈中
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

Scanner

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int[] stk = new int[N];
    static int tt;

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        for (int i = 0; i < m; i++){
            int x = scan.nextInt();
            while (i != 0 && stk[tt] >= x) --tt;
            if (tt == 0) System.out.print(-1 + " ");
            else System.out.print(stk[tt] + " ");
            stk[++tt] = x;
        }
    }
}