最小栈

难度:

标签:

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10⁴ 次

代码结果

运行时间: 34 ms, 内存: 19.4 MB

// Solution using Java Streams
 
/**
 * MinStack class provides a stack with the ability to retrieve the minimum element in constant time.
 */
import java.util.*;
import java.util.stream.*;
 
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
 
    /**
     * Initializes the stack and the minStack.
     */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
 
    /**
     * Pushes an element onto the stack.
     * If the minStack is empty or the element is smaller than or equal to the top of minStack,
     * push the element onto the minStack.
     *
     * @param val The value to push onto the stack.
     */
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
 
    /**
     * Removes the top element from the stack.
     * If the element being removed is equal to the top of the minStack, pop the minStack as well.
     */
    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }
 
    /**
     * Retrieves the top element of the stack.
     *
     * @return The top element of the stack.
     */
    public int top() {
        return stack.peek();
    }
 
    /**
     * Retrieves the minimum element in the stack.
     *
     * @return The minimum element in the stack.
     */
    public int getMin() {
        return minStack.peek();
    }
 
    /**
     * Retrieves all elements in the stack as a list.
     *
     * @return A list containing all elements in the stack.
     */
    public List<Integer> getStackAsList() {
        return stack.stream().collect(Collectors.toList());
    }
}

解释

方法:

该题解使用两个栈来实现最小栈，一个栈 stack 存储所有元素，另一个栈 min_stack 存储当前的最小元素。在 push 操作时，如果新元素小于等于 min_stack 的栈顶元素，就将新元素也压入 min_stack。在 pop 操作时，如果弹出的元素等于 min_stack 的栈顶元素，就将 min_stack 的栈顶元素也弹出。这样可以保证 min_stack 的栈顶元素始终是当前 stack 中的最小元素。

时间复杂度:

O(1)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在设计最小栈时选择使用两个栈来实现，而不是使用一个栈配合其他数据结构如哈希表或优先队列？

▷

使用两个栈来实现最小栈的主要优点是其简洁性和效率。使用两个栈可以在常数时间内完成所有操作，包括插入、删除和获取最小元素。如果使用哈希表，虽然可以快速访问元素，但不易于维护每个元素的最小值状态。使用优先队列（如最小堆）虽然可以快速获取最小值，但在删除非堆顶元素时效率较低，不适合本问题的需求，因为栈的元素删除顺序是后进先出，这与最小堆的操作不兼容。因此，使用两个栈是一种既简单又高效的设计策略。

🦆

在`pop`操作中，如果弹出的元素等于`min_stack`的栈顶元素时，为什么必须同时弹出`min_stack`的栈顶元素？

▷

这是因为`min_stack`的栈顶元素表示的是在主栈`stack`中所有元素的当前最小值。当`pop`操作发生时，如果弹出的元素等于`min_stack`的栈顶元素，这意味着栈中的最小元素被移除了。因此，为了维护`min_stack`的正确性，表示当前最小值的元素也必须从`min_stack`中移除。这样可以确保`min_stack`的栈顶元素始终是剩余元素中的最小值。

🦆

如果在`push`操作中，新压入的元素大于`min_stack`的栈顶元素，为什么选择不将其加入到`min_stack`？

▷

在`push`操作中，如果新压入的元素大于`min_stack`的栈顶元素，这意味着新元素对当前的最小元素没有影响，因为`min_stack`的栈顶元素已经是小于或等于新元素的最小值。将大于当前最小值的元素添加到`min_stack`中将无助于维护最小值状态，并且会增加不必要的空间占用。因此，只有当新元素小于或等于`min_stack`的栈顶元素时，才将其加入`min_stack`，以更新当前的最小值。

🦆

请问`getMin`操作返回`min_stack`的栈顶元素为什么能保证是当前栈中的最小元素？

▷

`getMin`操作返回`min_stack`的栈顶元素能保证是当前栈中的最小元素，因为`min_stack`是专门设计来在每个时刻存储`stack`中所有元素的最小值的。每次新元素入栈时，如果该元素小于或等于`min_stack`的栈顶元素，它就被加入`min_stack`。这样，无论何时，`min_stack`的栈顶元素都是`stack`中当前所有元素的最小值。因此，`getMin`操作直接返回`min_stack`的栈顶元素即可得到当前的最小值。

最小栈

题目描述

代码结果

解释

代码细节讲解

相关问题

滑动窗口最大值

最大栈