[Headline] Written test questions - minimum stack

Solution 1: (relative to solution 2, it will be very tasteless)

Thinking:

• Because the time complexity of obtaining the minimum element of the stack is O(1), all use a variable min to store the minimum value
• Set the variable min that stores the minimum value to Integer.MAX_VALUE
• In the push method, use min to compare each push
• Create two stacks, the first stack is used to store data, and the second stack is used to obtain the zero-hour stack with the minimum data through the first stack of variables

class MinStack {public Stack stack;public Stack stackTmp;public MinStack() {stack = new Stack<>();stackTmp = new Stack<>();}// first assign the maximum valuepublic int min = Integer.MAX_VALUE;public void push(int val) {// Assign a value if it is smaller than himif(val < min){min = val;}stack.push(val);}public void pop() {if(stack.pop() == min){//min needs to be reassigned after being popped, still using the maximum valuemin = Integer.MAX_VALUE;//Transfer all elements to stackTmp, the purpose is to make min re-comparison with all elementswhile(!stack.empty()){int tmp = stack.pop();if(tmp < min){min = tmp;}stackTmp.push(tmp);}// then move to stackwhile(!stackTmp.empty()){stack.push(stackTmp.pop());}}}public int top() {return stack.peek();}public int getMin() {return min;}}

---

Solution 2: (analysis is as follows)

​​

The code is as follows:

class MinStack {Stack stack;//Normal stackStack stackMin;//Minimum stackpublic MinStack() {stack = new Stack<>();stackMin = new Stack<>();}// push stackpublic void push(int val) {//Assign the initial value to the minimum stationif(stackMin.empty()){stackMin.push(val);}//If it is not the initial value, first judge whether it is less than or equal to (to prevent it from being empty after pop) the top element of the minimum stack, if so, push the stack to the minimum stackelse if(stackMin.peek() >= val){stackMin.push(val);}stack.push(val);}public void pop() {if((int)stackMin.peek() == (int)stack.peek()){stackMin.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return stackMin.peek();}}