# Design the smallest stack, that is, there are the basic operations of the stack, push, pop, peek, and the function of returning the minimum value in the stack, getMin

Tip: previously, we said that the system stack can push, pop and peek normally

Now we need to design a minimum stack, and the o(1) speed returns the minimum value in the current stack.

# subject

Design the minimum stack, that is, the basic operations of the stack push, pop, peek,

There is also a new function: getMin() that returns the minimum value in the current stack

# 1, Examining questions

Example: for example, press in 2 3 1 4 5

The corresponding minimum value in the stack should be:

2 2 1 1 1

Please implement such a stack: the smallest stack

# 2, Design method of minimum stack

In fact, the smallest stack can also be seen from the example, that is, two system stacks: data stack and min stack

data is responsible for daily push, pop and peek functions

Each time you push, you need to compare the new value and the value at the top of the stack in min

If:

(1) Value > = the value at the top of Min stack: you need to assign the top of Min stack to value and store it in min, which means that the minimum value has remained unchanged

(2) Value < min the value at the top of the stack: a new minimum value does come. Just store value in Min directly, which means that the new minimum value comes

In that case, data will do its own thing

Min ensures that the quantity is the same as that of data. Moreover, the minimum value of data in the current range is placed in min and will not be disordered

Just look at the picture

When there is only 2 in data, min must also be only 2, which is the minimum value

When there is 32 in the data, the minimum value is naturally 2,

When there is 132 in the data, a 1 is smaller than 2. Naturally, 1 will be the minimum from now on

If the subsequent number is greater than or equal to 1, 1 will naturally be stored at the top of the stack in min

Unless there is a 0 or smaller, let min put a smaller one

(3) When pop-up, data will perform its own routine operation, and then min will pop up one to ensure that the quantity within the range is consistent with data;

Hand tear Code:

//Review the minimum stack, very simple, is to take another system stack and put the minimum value entered each time public static class MinStack{ //Dual system stack public Stack<Integer> dataStack; public Stack<Integer> minStack; public MinStack(){ dataStack = new Stack<>(); minStack = new Stack<>(); } //isEmpty public boolean isEmpty(){ return dataStack.isEmpty(); } //push public void push(int value){ //You can play your own game normally dataStack.push(value); //The key is to judge the new value and the top of minStack if (minStack.isEmpty()) minStack.push(value);//The number that comes first must be the smallest else if (value >= minStack.peek()) { value = minStack.peek();//Re assign value and then add min. don't forget minStack.push(value); } else minStack.push(value);//If you skip the above if, it means that the smaller one is coming } //pop public int pop(){ //No error reporting if (dataStack.isEmpty()) throw new RuntimeException("No number!"); //min should be consistent with the data quantity and range, so a pop-up should be made first minStack.pop(); return dataStack.pop(); } //peek public int peek(){ //Report an error if there is no one if (dataStack.isEmpty()) throw new RuntimeException("No number!"); //It depends on the top of the stack. It has nothing to do with min return dataStack.peek(); } //Here comes the key function, getMin public int getMin(){ //No element, error reported if (minStack.isEmpty()) throw new RuntimeException("No number!"); //If yes, naturally, it will return to the top of minStack, which has nothing to do with data return minStack.peek(); } } public static void test2(){ MinStack stack = new MinStack(); stack.push(2); System.out.println("Current minimum:"+ stack.getMin());//2 stack.push(3); System.out.println("Current minimum:"+ stack.getMin());//2 stack.push(1); System.out.println("Current minimum:"+ stack.getMin());//1 stack.push(4); System.out.println("Current minimum:"+ stack.getMin());//1 stack.push(5); System.out.println("Current minimum:"+ stack.getMin());//1 System.out.println("Stack top data:"+ stack.peek());//5 System.out.println(stack.isEmpty()); System.out.println(stack.pop());//5 System.out.println("Current minimum:"+ stack.getMin());//1 System.out.println(stack.pop());//4 System.out.println("Current minimum:"+ stack.getMin());//1 System.out.println(stack.pop());//1 System.out.println("Current minimum:"+ stack.getMin());//2 System.out.println(stack.pop());//3 System.out.println("Current minimum:"+ stack.getMin());//2 System.out.println(stack.pop());//2 System.out.println(stack.isEmpty()); } public static void main(String[] args) { // test(); test2(); }

Look at the result, it's perfect:

Current minimum: 2 Current minimum: 2 Current minimum: 1 Current minimum: 1 Current minimum: 1 Stack top data: 5 false 5 Current minimum: 1 4 Current minimum: 1 1 Current minimum: 2 3 Current minimum: 2 2 true

# summary

Tip: important experience:

1) The smallest stack is nothing more than a stack that stores the minimum value. If it is replaced by the largest stack, it is estimated to be very simple

2) Use the underlying system data structure to realize the new data structure you want, which is the significance of learning data structure and algorithm. This is the essence of large factories to recruit you to enter the optimization algorithm and realize new business functions in the future.