题解 | #CD5 设计getMin功能的栈#

代码一

使用 BufferedReader 读取数据，io 输入时间大幅缩短，

• 运行时间：1348ms，超过 82.45% 用Java提交的代码
• 占用内存：21336KB，超过98.89% 用Java提交的代码

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    Deque<Integer> data = new LinkedList<>();
    Deque<Integer> min = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        // 使用 BufferedReader，InputStreamReader 改进读取数据的时间
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(sc.readLine());
        for(int i = 0; i < row; i++) {
            String s = sc.readLine();
            switch(s){
                case "pop":
                    mn.pop();
                    break;
                case "getMin":
                    mn.getMin();
                    break;
                default:
                    String[] ss = s.split(" ");
                    int n = Integer.valueOf(ss[1]);
                    mn.push(n);
                    break;
                    
            }
        }
    }
    
    private void push(int n) {
        data.push(n);
        if(!min.isEmpty()) {
            int curMin = min.peek();
            if (curMin < n){
                min.push(curMin);
            }else {
                min.push(n);
            }
        }else {
            min.push(n);
        }
            
    }
    
    private void getMin() {
        System.out.println(min.peek());
        
    }
    
    private void pop() {
        data.pop();
        min.pop();
    }
        
    
    
}

代码二

使用 Scanner 来读取数据，运行时间长，运行时间：2308ms 占用内存：25668KB

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    Deque<Integer> data = new LinkedList<>();
    Deque<Integer> min = new LinkedList<>();
    public static void main(String[] args) {
        Main mn = new Main();
        Scanner in = new Scanner(System.in);
        in.nextLine();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            switch(s){
                case "pop":
                    mn.pop();
                    break;
                case "getMin":
                    mn.getMin();
                    break;
                default:
                    String[] ss = s.split(" ");
                    int n = Integer.valueOf(ss[1]);
                    mn.push(n);
                    break;
                    
            }
        }
    }
    
    private void push(int n) {
        data.push(n);
        if(!min.isEmpty()) {
            int curMin = min.peek();
            // 每次输入都会保存一份最小数据，这样在跑pop 的时候比较快
            if (curMin < n){
                min.push(curMin);
            }else {
                min.push(n);
            }
        }else {
            min.push(n);
        }
            
    }
    
    private void getMin() {
        System.out.println(min.peek());
        
    }
    
    private void pop() {
        data.pop();
        min.pop();
    }
        
    
    
}