Algorithm illustration: How do I find the minimum value in the stack?

We learned a lot about stacks earlier, such as Motion Picture Demonstration: Two Implementations of the Hand Stack! H ow did JDK implement the stack? Then let's brush some classic interview questions about stacks to reinforce what we've learned.

Our interview question today is like this...

topic

To define the data structure of the stack, implement a min function in that type that can get the smallest element of the stack, where 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(); -- > Return -3.

minStack.pop();

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

minStack.min(); -- > Return -2.

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

ponder

First of all, the topic itself is well understood, its implementation difficulties lie in the following two aspects:

• How do we find the next minimum value when we do pop (remove top-of-stack elements) if the current minimum value is removed?
• To ensure that the time complexity of calling min, push, and pop is O(1).

That is, if the smallest value in the stack is removed when we execute pop, how do we find the next smallest element in the stack? A lso ensure that the time complexity of the operation is O(1). This time complexity prevents us from finding the next minimum value by traversing after removing the minimum value, so this becomes a difficult problem for this question.

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 image:

So next, let's think about it for 3 minutes and think about how we should deal with it

The idea of solving the problem

In fact, we can determine whether the current element is less than the minimum value each time we enter the stack, and if it is less than, the original minimum value and the latest minimum value are stacked one after another, so that even if the minimum value is removed when pop is called, we can get a new minimum value by getting the next element, as shown in the execution process.

Step 1

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

Step 2

The second element in the stack, as shown in the following image:

Because the element in the stack is smaller than 8, the original minimum value of 8 in the stack is stored in the stack, and then 3 is put into the stack.

Step 3

The third element in the stack, as shown in the following image:

Because the in-stack element 5 is greater than 3, the minimum value in the stack remains the same and the element 5 is put directly into the stack.

Procedure 4

Continue to the stack, as shown in the following image:

"In-stack element 1 is less than 3, so the original minimum value of 3 is put into the stack, and then 1 is put into the stack, and the minimum value in the stack is changed to 1."

Procedure 5

Do the out-of-stack operation, as shown in the following image:

Element 1 comes out of the stack to determine that the current element is the minimum value of the stack, so set the top element 3 to the minimum and remove element 3, as shown in the following image:

Step 6

Continue out of the stack, as shown in the following image:

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

Procedure 7

Continue out of the stack, as shown in the following image:

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

This leaves the last element, and when the last element comes out of the stack, it becomes an empty stack, and the whole process is complete.

Implement code 1

Next we'll implement the above idea in code, and we'll implement the relevant functionality with the stack implemented by the array, as follows:

class MinStack {
    private int[] data; // 栈数据
    private int maxSize; // 最大长度
    private int top; // 栈顶指针（下标）
    private int min; // 最小值


    // 构造函数
    public MinStack() {
        // 设置默认值
        maxSize = 10000;
        data = new int[maxSize];
        top = -1;
        min = Integer.MAX_VALUE;
    }


    // 入栈（添加元素）
    public void push(int x) {
        if (min >= x) {
            // 遇到了更小的值，记录原最小值（入栈）
            data[++top] = min;
            min = x;
        }
        // 当前值入栈
        data[++top] = x;
    }


    // 出栈（移除栈顶元素）
    public void pop() {
        if (min == data[top]) {
            min = data[--top]; // 拿到原最小值，并（将原最小值）出栈
        }
        --top; // 出栈
    }


    // 查找栈顶元素
    public int top() {
        return data[top];
    }

 
    // 查询最小值
    public int min() {
        return min;
    }
}

The above code is executed in LeetCode as follows:

You can see that performance is still high, surpassing 99.92% of users and not consuming much memory. I ts core code, within the push method, first puts the original minimum value and the latest minimum value into the stack one after the other, determines whether the stack element is the minimum value when pop out of the stack, and points the current minimum value to the top of the stack element and out of the stack element if it is the minimum value, thus getting the next new minimum value.

Implement code 2

If we don't want to implement this using a custom stack for arrays, we can also do this with the stack Stack that comes with Java, as follows:

class MinStack {
    private Stack stack = new Stack();
    private int min = Integer.MAX_VALUE;


    public MinStack() { }


    // 入栈（添加元素）
    public void push(int x) {
        if (x  这种实现代码的方式（使用 Java API），在刷题或者实际面试中如果没有特殊说明是可以直接用的。


### 总结


本文我们通过两种方式：自定义数组栈和 Java API 中的 `Stack` 来实现了栈中最小值的功能，保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1)。两种实现方式的代码虽然略不相同，但实现思路都是一样的，都是**在元素入栈时判断当前元素是否小于最小元素，如果小于最小元素则先将原最小值入栈，再将当前最小元素入栈，这样当调用 pop 方法时，即使移除的是最小值，只需要将下一个元素取出即为新的最小值了**，这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。


>文章来源于公众号：Java中文社群 作者：磊哥


以上就是`W3Cschool编程狮`关于**算法图解：如何找出栈中的最小值？**的相关介绍了，希望对大家有所帮助。