What is the way to find out the minimum value in the stack

This article introduces the relevant knowledge of "what is the method of finding the minimum value in the stack". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Title

To define the data structure of the stack, implement a min function in this type that can get the smallest elements of the stack. In this stack, the time complexity of calling min, push, and pop is O (1).

Example:

MinStack minStack = new MinStack ()

MinStack.push (- 2)

MinStack.push (0)

MinStack.push (- 3)

MinStack.min ();-- > returns-3.

MinStack.pop ()

MinStack.top ();-- > returns 0.

MinStack.min ();-- > returns-2.

LeetCode address: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

Thinking

First of all, the topic itself is easy to understand, and the difficulty of its implementation lies in the following two aspects:

When we pop (remove Top Stack elements), if we delete the current minimum, how do we find the next minimum?

Make sure that the time complexity of calling min, push, and pop is O (1).

That is, if we remove the smallest value from the stack when we execute pop, how do we find the next smallest element in the stack? And the time complexity of the operation should be guaranteed to be O (1). This time complexity restricts that we can not find the next minimum value by traversing after removing the minimum value, so this becomes the difficulty of this problem.

For example, when we remove the following stack top element values:

Because the minimum value is 1, the minimum value is also removed after removal, as shown in the following figure:

So next, let's think about it for 3 minutes and think about how to deal with this problem.

Problem-solving ideas

In fact, each time we enter the stack, we can determine whether the current element is less than the minimum value, and if so, the original minimum value and the latest minimum value will be entered into the stack one after another, so that even if the minimum value is removed when calling pop, we can still get a new minimum value by getting the next element. The execution process is as follows.

Operation step 1

The first element on the stack, because it is the first element, so the minimum value is the value of this element.

Operation step 2

Enter the second element in the stack, as shown in the following figure:

Because the element 3 is smaller than 8, the original minimum value of 8 in the stack is first stored in the stack, and then 3 is added to the stack.

Operation step 3

Enter the third element in the stack, as shown in the following figure:

Because element 5 is greater than 3, the minimum value in the stack remains the same, and element 5 is added directly to the stack.

Operation step 4

Continue to stack, as shown in the following figure:

The stack element 1 is greater than 3, so the original minimum value of 3 is added to the stack, and then 1 is added to the stack, and the minimum value in the stack is changed to 1.

Operation step 5

Perform the unstack operation, as shown in the following figure:

Element 1 goes out of the stack and determines that the current element is the minimum value of the stack, so set element 3 at the top of the stack to the minimum value and remove element 3, as shown in the following figure:

Operation step 6

Continue to unstack, as shown in the following figure:

Because element 5 is not the current minimum, it goes straight out of the stack.

Operation step 7

Continue to unstack, as shown in the following figure:

Because out-of-stack element 3 is the minimum, continue to set the minimum to top-of-stack element 8 and unstack the top-of-stack element, as shown in the following figure:

This leaves the last element, which becomes empty after the last element is released from the stack, and the whole process is executed.

Implementation code 1

Next, let's implement the above idea in code. We use the stack implemented by the array to implement the related functions. The code is as follows:

Class MinStack {private int [] data; / / Stack data private int maxSize; / / maximum length private int top; / / Stack Top pointer (subscript) private int min; / / minimum / / Constructor public MinStack () {/ / set default value maxSize = 10000; data = new int [maxSize]; top =-1 Min = Integer.MAX_VALUE;} / / Stack (add element) public void push (int x) {if (min > = x) {/ / encountered a smaller value, record the original minimum value (stack) data [+ + top] = min; min = x } / / the current value is put into the stack data [+ + top] = x;} / / public void pop () {if (min = = data [top]) {min = data [--top]; / / get the original minimum value and (take the original minimum value) out of the stack}-- top / / out the stack} / / find the top element public int top () {return data [top];} / / query the minimum value public int min () {return min;}}

The execution result of the above code in LeetCode is as follows:

It can be seen that the performance is still very high, exceeding 99.92% of users, and the memory consumption is not large. Its core code is in the push method, first put the original minimum value and the latest minimum value into the stack one after another, judge whether the stack element is the minimum value when the pop is out of the stack, if it is the minimum value, point the current minimum value to the top element of the stack and unstack the top element of the stack, so you get the next new minimum value.

Implementation code 2

If we do not want to use the custom stack of the array, we can also use the stack Stack that comes with Java to achieve this function, as follows:

Class MinStack {private Stackstack = new Stack (); private int min = Integer.MAX_VALUE; public MinStack () {} / / stack (add elements) public void push (int x) {if (x)