155.最小栈

题目:155.最小栈

• 示例 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^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10^4 次

思路

为了设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈，我们可以使用两个栈来实现。一个栈用于存储所有的元素，另一个栈用于存储每一步操作后的最小元素。

具体的思路如下：

1. **主栈 (normalStack)**：用于存储所有被压入的元素。
2. **辅助栈 (minStack)**：用于存储与主栈同步的最小值。

在每次 push 操作时：

• 将元素压入主栈。
• 比较元素与当前 minStack 栈顶的元素，如果新元素更小或等于栈顶元素，则将其也压入 minStack。

在每次 pop 操作时：

• 将主栈栈顶元素弹出。
• 如果这个元素等于 minStack 的栈顶元素，那么 minStack 也要同时弹出栈顶元素。

这样，getMin 操作可以直接通过访问 minStack 的栈顶元素来获取当前最小值，时间复杂度为 O(1)。

• 时间复杂度:O(1)
• 空间复杂度:O(1)

代码

public class MinStack {
    Stack<Integer> normalStack;
    Stack<Integer> minStack;

    // 构造方法，初始化两个栈
    public MinStack() {
        normalStack = new Stack<>();
        minStack = new Stack<>();
    }

    // 压栈操作
    public void push(int val) {
        normalStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    // 弹栈操作
    public void pop() {
        Integer pop = normalStack.pop();
        if (!minStack.isEmpty() && pop.equals(minStack.peek())) {
            minStack.pop();
        }
    }

    // 获取栈顶元素
    public int top() {
        return normalStack.peek();
    }

    // 获取最小元素
    public int getMin() {
        return minStack.peek();
    }
}