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

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.

Tags: Java data structure leetcode

Posted by dragon_sa on Sun, 01 May 2022 01:52:25 +0300