程序员代码面试指南
链接
思路1
设计两个栈，一个栈stackData负责存取原始数据，另一个栈stackMin负责存取最小数来实现getMin功能。
1）push规则：假设当前数据为newNum，先将其压入stackData，然后判断和stackMin的栈顶元素哪一个更小，若newNum小于等于，则也将其压入stackMin，否则stackMin不压入元素。若stackMin为空，newNum也压入stackMin。
2）pop规则：先从stackData中弹出栈顶元素，然后判断这个弹出值和stackMin的栈顶元素哪个更小，由压入性质可知，stackMin中的元素从栈顶到栈底是由小变大的，stackMin的栈顶值是两个栈中共同的最小值。所以此时，stackData的值不会比stackMin的栈顶值还小，只有可能等于或者大于。所以当等于的时候，也把stackMin的栈顶元素弹出。
3）getMin规则：由2）的分析可知，getMin的栈顶元素始终为stackData中目前的最小值，所以取栈顶元素就可以。
import java.util.Stack;
import java.util.Scanner;
public class Main{private Stack<Integer> stackData;private Stack<Integer> stackMin;public Main() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum) {if(this.stackMin.isEmpty()) {this.stackMin.push(newNum);}else if(newNum <= this.getMin()) {this.stackMin.push(newNum);}this.stackData.push(newNum);}public int pop() {if(this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}int value = this.stackData.pop();if(value == this.getMin()) {this.stackMin.pop();}return value;}public int getMin() {if(this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int count = sc.nextInt();Main stack = new Main();for(int i = 0; i<count; i++) {String op = sc.next();if(op.equals("push")) {int x = sc.nextInt();stack.push(x);}else if(op.equals("pop")) {stack.pop();}else if(op.equals("getMin")) {System.out.println(stack.getMin());}}}
}思路2
还是跟1一样设计两个栈，区别在于，压入时，比较newNum和stackMin的栈顶元素，若栈顶元素更大，则重复在stackMin中压入栈顶元素。在弹出时，stackMin不管如何也一起随着stackData弹出栈顶元素。
import java.util.Stack;
import java.util.Scanner;class MyStack {private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum) {if(this.stackMin.isEmpty()) {this.stackMin.push(newNum);}else if(newNum <= this.getMin()) {this.stackMin.push(newNum);}else {this.stackMin.push(this.stackMin.peek());}this.stackData.push(newNum);}public int pop() {if(this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}this.stackMin.pop();return this.stackData.pop();}public int getMin() {if(this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}
}public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);MyStack stack = new MyStack();int count = sc.nextInt();for(int i=0; i<count; i++) {String op = sc.next();if(op.equals("push")) {int x = sc.nextInt();stack.push(x);}else if(op.equals("pop")) {stack.pop();}else if(op.equals("getMin")) {System.out.println(stack.getMin());}}}
}总结
牛客的ACM模式是不提供输入输出的，需要自己写出main函数进行输入输出的处理
程序员代码面试指南
链接
思路1
设计两个栈，一个栈stackData负责存取原始数据，另一个栈stackMin负责存取最小数来实现getMin功能。
1）push规则：假设当前数据为newNum，先将其压入stackData，然后判断和stackMin的栈顶元素哪一个更小，若newNum小于等于，则也将其压入stackMin，否则stackMin不压入元素。若stackMin为空，newNum也压入stackMin。
2）pop规则：先从stackData中弹出栈顶元素，然后判断这个弹出值和stackMin的栈顶元素哪个更小，由压入性质可知，stackMin中的元素从栈顶到栈底是由小变大的，stackMin的栈顶值是两个栈中共同的最小值。所以此时，stackData的值不会比stackMin的栈顶值还小，只有可能等于或者大于。所以当等于的时候，也把stackMin的栈顶元素弹出。
3）getMin规则：由2）的分析可知，getMin的栈顶元素始终为stackData中目前的最小值，所以取栈顶元素就可以。
import java.util.Stack;
import java.util.Scanner;
public class Main{private Stack<Integer> stackData;private Stack<Integer> stackMin;public Main() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum) {if(this.stackMin.isEmpty()) {this.stackMin.push(newNum);}else if(newNum <= this.getMin()) {this.stackMin.push(newNum);}this.stackData.push(newNum);}public int pop() {if(this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}int value = this.stackData.pop();if(value == this.getMin()) {this.stackMin.pop();}return value;}public int getMin() {if(this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int count = sc.nextInt();Main stack = new Main();for(int i = 0; i<count; i++) {String op = sc.next();if(op.equals("push")) {int x = sc.nextInt();stack.push(x);}else if(op.equals("pop")) {stack.pop();}else if(op.equals("getMin")) {System.out.println(stack.getMin());}}}
}思路2
还是跟1一样设计两个栈，区别在于，压入时，比较newNum和stackMin的栈顶元素，若栈顶元素更大，则重复在stackMin中压入栈顶元素。在弹出时，stackMin不管如何也一起随着stackData弹出栈顶元素。
import java.util.Stack;
import java.util.Scanner;class MyStack {private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum) {if(this.stackMin.isEmpty()) {this.stackMin.push(newNum);}else if(newNum <= this.getMin()) {this.stackMin.push(newNum);}else {this.stackMin.push(this.stackMin.peek());}this.stackData.push(newNum);}public int pop() {if(this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}this.stackMin.pop();return this.stackData.pop();}public int getMin() {if(this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}
}public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);MyStack stack = new MyStack();int count = sc.nextInt();for(int i=0; i<count; i++) {String op = sc.next();if(op.equals("push")) {int x = sc.nextInt();stack.push(x);}else if(op.equals("pop")) {stack.pop();}else if(op.equals("getMin")) {System.out.println(stack.getMin());}}}
}总结
牛客的ACM模式是不提供输入输出的，需要自己写出main函数进行输入输出的处理
发布评论