单调栈-算法

单调栈用法1 ： 寻找一个数左边第一个小于它的数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] a = new int[n];
        int[] ans = new int[n];
        Deque<Integer> stk = new LinkedList<>();
        for(int i = 0;i<n;i++){
            a[i] = sc.nextInt();
        }
        for(int i = 0;i<n;i++){
            while(!stk.isEmpty() && stk.peek() >= a[i]) {
                stk.pop();
            }
            if(!stk.isEmpty()) {
                ans[i] = stk.peek();
            }
            else {
                ans[i] = -1;
            }
            stk.push(a[i]);
        }
        for(int i = 0;i<n;i++){
            System.out.print(ans[i] + " ");
        }
    }
}

ChatGpt写得注释

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] ans = new int[n];
        Deque<Integer> stk = new LinkedList<>(); // 创建一个双端队列

        // 输入数组
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 单调栈模板
        for (int i = 0; i < n; i++) {
            while (!stk.isEmpty() && stk.peek() >= a[i]) { // 队列非空并且当前元素小于等于队头元素
                stk.pop(); // 弹出队头元素，保证队列的单调性
            }
            if (!stk.isEmpty()) { // 队列非空，当前元素左边有比它小的元素
                ans[i] = stk.peek(); // 当前元素左边第一个比它小的元素为队头元素
            } else {
                ans[i] = -1; // 队列为空，当前元素左边没有比它小的元素
            }
            stk.push(a[i]); // 将当前元素压入队头
        }

        // 输出结果数组
        for (int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}

暴力

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }

        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    flag = true;
                    System.out.print(a[j] + " ");
                    break;
                }
            }
            if (!flag) {
                System.out.print(-1 + " ");
            }
        }
    }
}