面试经典单调栈进阶之java版

思路

单调栈：一次遍历、两次遍历
然而单调栈只能过75%，，隔壁中心扩展居然能过？？？？？？
修改输入，用buffer，90%-95%,

函数版

import java.util.*;
public class Main{
    public static int[][] help(int[] in){
        int[][] res=new int[in.length][2];
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<in.length;i++){
            while(!stack.isEmpty() && in[stack.peek()]>in[i]){
                int k=stack.pop();
                res[k][1]=i;
            }
            res[i][0]=stack.isEmpty()?-1:
            (in[stack.peek()]==in[i]?res[stack.peek()][0]:stack.peek());
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()][1] = -1;
        }
        return res;
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] in=new int[n];
        for(int i=0;i<n;i++){
            in[i]=sc.nextInt();
        }
        int[][] res=help(in);
        for(int i=0;i<n;i++){
            System.out.println(res[i][0]+" "+res[i][1]);
        }
    }
}

修改输入

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] in=Arrays.stream(reader.readLine().split(" "))
             .parallel().mapToInt(Integer::parseInt).toArray();
        int[][] res=new int[n][2];
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty() && in[stack.peek()]>in[i]){
                int k=stack.pop();
                res[k][1]=i;
            }
            res[i][0]=stack.isEmpty()?-1:
            (in[stack.peek()]==in[i]?res[stack.peek()][0]:stack.peek());
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()][1] = -1;
        }

        for(int i=0;i<n;i++){
            System.out.println(res[i][0]+" "+ res[i][1]);
        }
    }
}