Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to find the minimum value in the stack," interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "how to find the minimum value in the stack"!

topic

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

Examples:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> back to-3. minStack.pop(); minStack.top (); --> returns 0. minStack.min(); --> Return-2. LeetCode Address: leetcode-cn.com/problems/ba…

thinking

First of all, this topic itself is very easy to understand, and its implementation difficulties lie in the following two aspects:

When we pop(remove top element), if we delete the current minimum, how do we find the next minimum?

The time complexity of calling min, push and pop is O(1).

That is, if we remove the smallest value in the stack when we perform pop, how do we find the next smallest element in the stack? The time complexity of the algorithm is O(1). This time complexity prevents us from traversing to find the next minimum after removing the minimum, so this becomes the difficulty of the problem.

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

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

那么接下来，让我们一起思考 3 分钟，想一想应该如何处理这个问题~

解题思路

其实我们可以在每次入栈时，判断当前元素是否小于最小值，如果小于则将原最小值和最新的最小值相继入栈，这样在调用 pop 时即使移除的是最小值，我们也能通过获取下一个元素得到一个新的最小值，执行流程如下所示。

操作步骤1

入栈第一个元素，因为是第一个元素，因此最小值就是此元素的值。

操作步骤2

入栈第二个元素，如下图所示：

因为入栈的元素 3 比 8 小，所以先将栈中的原最小值 8 存入栈中，再将 3 入栈。

操作步骤3

入栈第三个元素，如下图所示：

因为入栈元素 5 大于 3，因此栈中的最小值不变，直接将元素 5 入栈。

操作步骤4

继续入栈，如下图所示：

入栈元素 1 小于 3，因此先将原最小值 3 入栈，再将 1 入栈，栈中的最小值更改为 1。

操作步骤5

执行出栈操作，如下图所示： [图片上传中...(image-f68dcf-1602769401330-6)]

元素 1 出栈，判断当前元素就是栈的最小值，因此将栈顶元素 3 设置为最小值，并移除元素 3，如下图所示：

操作步骤6

继续出栈，如下图所示：

因为元素 5 不是当前最小值，因此直接出栈。

操作步骤7

继续出栈，如下图所示：

因为出栈元素 3 为最小值，因此继续将最小值设置为栈顶元素 8，并将栈顶元素出栈，如下图所示：

这样就剩下最后一个元素了，最后一个元素出栈之后就成空栈了，整个流程就执行完了。

实现代码1

接下来我们将上面的思路用代码实现一下，我们用数组实现的栈来实现相关的功能，代码如下：

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; } }

上述代码在 LeetCode 的执行结果如下：

可以看出性能还是很高的，超越了 99.92% 的用户，内存消耗也不大。它的核心代码在 push 方法内，先将原最小值和最新最小值相继入栈，在 pop 出栈时判断出栈元素是否为最小值，如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈，这样就得到了下一个新的最小值了。

实现代码2

如果我们不想使用数组的自定义栈来实现，还可以使用 Java 中自带的栈 Stack 来实现此功能，代码如下：

class MinStack { private Stack stack = new Stack(); private int min = Integer.MAX_VALUE; public MinStack() { } // 入栈（添加元素） public void push(int x) { if (x

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.