Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I want to clarify that every algorithm problem has multiple solutions, and we’ll just talk about a few excellent solutions in LeetCode ~, hopefully

Can help you, that we first look at the topic description ~

I. Title Description:

Design a stack push(x) that supports push, pop, and top operations and can retrieve the smallest element in constant time — push element X onto the stack. Pop () — Removes the top element of the stack. Top () — Gets the top element on the stack. GetMin () — Retrieves the smallest element in the stack.

Ii. Analysis of Ideas:

First of all, we know that the stack is first and last, so if an element A is pushed onto the stack with elements B, C, and D already in it, then no matter what the stack does later, as long as a is on the stack, b, C, and D must be on the stack; This way we can store the minimum value m of the current stack as each element A is pushed. Any time after that, if the top element on the stack is A, we can just return the minimum value of the store, m. With this in mind, we can use a secondary stack that inserts and deletes in sync with the element stack to store the minimum value corresponding to each element. When an element is to be pushed, we take the minimum value stored at the top of the current auxiliary stack, compare with the current element to get the minimum value, and insert this minimum value into the auxiliary stack. When an element goes off the stack, we pop the top element of the secondary stack. At any given moment, the minimum value of the element in the stack is stored in the top element of the secondary stack.

Iii. Code summary

class MinStack { Deque<Integer> myStack; Deque<Integer> minStack; public MinStack(){ myStack = new LinkedList<>(); minStack = new LinkedList<>(); minStack.push(Integer.MAX_VALUE); } public void push(int x){ myStack.push(x); minStack.push(Math.min(minStack.peek(),x)); Public void pop(){mystack.pop (); minStack.pop(); } public int top(){return mystack.peek (); } public int getMin(){return minstack.peek (); }}Copy the code

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together