2、维护单调栈

AcWing 830. 单调栈

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.dandiaozhan();

    }

    int N = 100010;
    Stack<Integer> stack = new Stack();

    //维护单调栈
    void dandiaozhan() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if (!stack.empty()) {
                if (stack.peek() >= nums[i]) {
                    while (!stack.empty() && stack.peek() >= nums[i]) {
                        stack.pop();
                    }
                    if (!stack.empty()) System.out.print(stack.peek() + " ");
                    else System.out.print(-1+" ");
                    stack.push(nums[i]);
                } else {
                    System.out.print(stack.peek() + " ");
                    stack.push(nums[i]);
                }
            } else {
                System.out.print(-1 + " ");
                stack.push(nums[i]);
            }
        }
    }
}