设计一个有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();
}
}
}
}遇到了问题,提交几次都是失败的,后来提交又成功了,什么鬼。。

