设计一个有getMin的栈
设计getMin功能的栈
http://www.nowcoder.com/questionTerminal/05e57ce2cd8e4a1eae8c3b0a7e9886be
方法一:
import java.util.Stack; import java.util.Scanner; public class Main{ private Stack<Integer> numStack; private Stack<Integer> minStack; public Main(){ numStack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int num){ if(minStack.isEmpty()){ minStack.push(num); }else{ //int min = minStack.peek(); //min = (num < min) ? num : min; int min = Math.min(minStack.peek(),num); minStack.push(min); } numStack.push(num); } public int pop(){ if(numStack.isEmpty()){ throw new RuntimeException("stack is empty!"); } minStack.pop(); return numStack.pop(); } public int getMin(){ if(minStack.isEmpty()){ throw new RuntimeException("stack is empty!"); } return minStack.peek(); } public static void main(String[] args){ Main myClass = new Main(); Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); scanner.nextLine(); String[] line; for(int i = 0; i < N; i++){ line = scanner.nextLine().split(" "); if(line[0].equals("getMin")){ System.out.println(myClass.getMin()); }else if(line[0].equals("push")){ myClass.push(Integer.valueOf(line[1])); }else{ myClass.pop(); } } } }
方法2:
import java.util.Stack; import java.util.Scanner; public class Main{ private Stack<Integer> numStack; private Stack<Integer> minStack; public Main(){ numStack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int num){ if(minStack.isEmpty()){ minStack.push(num); }else if(num <= getMin()){ minStack.push(num); } numStack.push(num); } public int pop(){ if(numStack.isEmpty()){ throw new RuntimeException("stack is empty!"); } int value = numStack.pop(); if(value == getMin()){ minStack.pop(); } // if(numStack.peek() == minStack.peek()){ // minStack.pop(); //} return value; } public int getMin(){ if(minStack.isEmpty()){ throw new RuntimeException("stack is empty!"); } return minStack.peek(); } public static void main(String[] args){ Main myClass = new Main(); Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); scanner.nextLine(); String[] line; for(int i = 0; i < N; i++){ line = scanner.nextLine().split(" "); if(line[0].equals("getMin")){ System.out.println(myClass.getMin()); }else if(line[0].equals("push")){ myClass.push(Integer.valueOf(line[1])); }else{ myClass.pop(); } } } }
遇到了问题,提交几次都是失败的,后来提交又成功了,什么鬼。。