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

单调栈结构(进阶)

http://www.nowcoder.com/questionTerminal/2a2c00e7a88a498693568cef63a4b7bb

思路

单调栈:一次遍历、两次遍历
然而单调栈只能过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]);
        }
    }
}
全部评论

相关推荐

06-07 21:26
江南大学 C++
话不多说,直接上时间线和图片1.2024年10月底发offer,并签三方2.2025年5月底公司违约
从零开始的转码生活:希望所有签了三方但直接违约的公司都倒闭!都倒闭!都倒闭!
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务