1.设计具有getMin功能的栈；

1.使用系统栈实现
2.模拟栈实现   

使用系统栈

 //准备两个栈
 private Stack<Integer> stackData; //正常data栈
 private Stack<Integer> stackMin; //当前data栈的最小值

 //1. 分析先实现getMin
 int getMin() {
 	return stackMin.pop();
 }
 
 //2. pop()
 int pop() {
 	int val = stackData.pop(); //题目保证不空
     if (val == getMin()) {
     	stackMin.pop();
     }
     return val;
 }
 
 //3. push()
 int push(int val) {
 	stackData.push(val); //数据必定要进data栈
     if (stackMin.isEmpty() || val <= getMin) { //使用 = 可以减少pop的设计复杂度
     	stackMin.push(val);
     }
 }
 ```
 
**模拟栈**

 ```
 /*
 例： 
 int stk[MAX]; //栈
 int tt = -1; //栈顶指针
 if (tt < 0) {...} //判空
 stk[++ tt] = ? //入栈
 tt --; //出栈
 ? = stk[tt]; //栈顶
 
 */
 
 static int[] stk = new int[1000010];
 static int tt = 1;
 static int[] min = new int[1000010];
 static int mm = -1;
 
 void push(int newNum) {
     if (mm < 0 || getMin() >= newNum) {
         min[++ mm] = newNum;
     }
     stk[++ tt] = newNum;
 }

 int pop() {
    if(stk[tt] == getMin()) {
        mm --;
    }
    return stk[tt --];
 }

 int getMin() {
     return min[mm];
 }
 ```
 
## 2.常用输入模板的使用，速度从2800+毫秒 ——> 400ms

**1系统栈**
``` java
import java.util.Stack;
import java.io.PrintWriter;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
 public static void main(String[] args) {
     Main stack = new Main();

     InputReader reader = new InputReader();
     PrintWriter out = new PrintWriter(System.out);

     reader.nextLine();
     int N = reader.nextInt();

     for (int i = 0; i < N; i++) {
         reader.nextLine();
         String op = reader.next();
         switch(op) {
             case "push":
                 stack.push(reader.nextInt());
                 break;
             case "getMin":
                 out.println(stack.getMin());
                 break;
             default:
                 stack.pop();
         }
     }
     out.close();
 }

 //=================================================
 private Stack<Integer> stackData; //正常数据栈
 private Stack<Integer> stackMin; //当前stackData最小值

 public Main() {
     stackData = new Stack<>();
     stackMin = new Stack<>();
 }

 public void push(int newNum) {
     if (stackMin.isEmpty() || this.getMin() >= newNum){
         stackMin.push(newNum);
     }
     stackData.push(newNum);
 }

 public int pop() {
    int value = stackData.pop();
    if (value == this.getMin()) {
        stackMin.pop();
    }
    return value;
 }

 public int getMin() {
     return stackMin.peek();
 }
}

//=================================================

/**
* 常用输入模板
*/
class InputReader {

 BufferedReader buf;
 StringTokenizer tok;

 InputReader() {
     buf = new BufferedReader(new InputStreamReader(System.in));
 }

 boolean hasNext() {
     while (tok == null || !tok.hasMoreElements()) {
         return false;
     }
     return true;
 }
 void nextLine(){
     try {
         tok = new StringTokenizer(buf.readLine());
     } catch (Exception e) {
         tok = null;
     }
 }

 String next() {
     if (hasNext()) return tok.nextToken();
     return null;
 }

 int nextInt() {
     return Integer.parseInt(next());
 }
}

数组模拟栈

import java.io.PrintWriter;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    static int[] stk = new int[1000010];
    static int tt = 1;
    static int[] min = new int[1000010];
    static int mm = -1;
    
    public static void main(String[] args) {
        Main stack = new Main();
        InputReader reader = new InputReader();
        PrintWriter out = new PrintWriter(System.out);

        reader.nextLine();
        int N = reader.nextInt();

        for (int i = 0; i < N; i++) {
            reader.nextLine();
            String op = reader.next();
            switch(op) {
                case "push":
                    stack.push(reader.nextInt());
                    break;
                case "getMin":
                    out.println(stack.getMin());
                    break;
                default:
                    stack.pop();
            }
        }
        out.close();
    }
  
	//=================================================
    public void push(int newNum) {
        if (mm < 0 || getMin() >= newNum) {
            min[++ mm] = newNum;
        }
        stk[++ tt] = newNum;
    }

    public int pop() {
       if(stk[tt] == getMin()) {
           mm --;
       }
       return stk[tt --];
    }

    public int getMin() {
        return min[mm];
    }
}
//=================================================

/**
 * 常用输入模板
 */
class InputReader {

    BufferedReader buf;
    StringTokenizer tok;

    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }

    boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            return false;
        }
        return true;
    }
    void nextLine(){
        try {
            tok = new StringTokenizer(buf.readLine());
        } catch (Exception e) {
            tok = null;
        }
    }

    String next() {
        if (hasNext()) return tok.nextToken();
        return null;
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
}