JAVA 单调栈习题解析

单调栈

问题描述

给定一个长度为 NN 的序列 aa。

第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。

第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。

第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。

第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。

update：本题数据于 2025-01-13 加强至 2×1052×105，以杜绝暴力通过。

输入格式

第一行输入一个正整数 NN。(1≤N≤2×105)(1≤N≤2×105)

第二行输入 NN 个正整数，表示序列 aa。(1≤ai≤105,1≤i≤N)(1≤a**i≤105,1≤i≤N)

输出格式

第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。

第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。

第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。

第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。

样例输入

5
4 3 2 1 5

样例输出

-1 4 3 2 -1
5 5 5 5 -1
-1 -1 -1 -1 1
3 2 1 -1 -1

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack =new ArrayDeque<>();//使用双端队列，实现单调栈
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++) {
            array[i] = scan.nextInt();
        }
        int[] leftbigger = new int[n];
        int[] rightbigger = new int[n];
        int[] leftsmaller = new int[n];
        int[] rightsmaller = new int[n];

        Arrays.fill(leftbigger,-1);
        Arrays.fill(rightbigger,-1);
        Arrays.fill(leftsmaller,-1);
        Arrays.fill(rightsmaller,-1);

        for(int i=0;i<n;i++) {
            while(!stack.isEmpty() && array[stack.peek()]<=array[i]){//保证stack里存的是大的，不是就要pop出来。
                stack.pop();
            }
            if(!stack.isEmpty()) {
                leftbigger[i] = array[stack.peek()];
            }

            stack.push(i);

        }
        stack.clear();

        for(int i=n-1;i>=0;i--) {
            while(!stack.isEmpty()&&array[stack.peek()]<=array[i]){//保证stack里存的是大的，不是就要pop出来。
                stack.pop();
            }
            if(!stack.isEmpty()) {
                rightbigger[i] = array[stack.peek()];
            }

            stack.push(i);

        }
        stack.clear();

        for(int i=0;i<n;i++) {
            while(!stack.isEmpty()&&array[stack.peek()]>=array[i]){//保证stack里存的是小的，不是就要pop出来。
                stack.pop();
            }
            //刚开始栈为空
            if(!stack.isEmpty()) {
                leftsmaller[i] = array[stack.peek()];
            }

            stack.push(i);

        }
        stack.clear();

        for(int i=n-1;i>=0;i--) {
            while(!stack.isEmpty()&&array[stack.peek()]>=array[i]){//保证stack里存的是xiao的，不是就要pop出来。
                stack.pop();
            }
            if(!stack.isEmpty()) {
                rightsmaller[i] = array[stack.peek()];
            }

            stack.push(i);

        }
        stack.clear();



       display(leftbigger);
        display(rightbigger);
        display(leftsmaller);
        display(rightsmaller);

        scan.close();
    }
    private static void display(int[] array) {
        for(int i=0;i<array.length;i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

}