题目描述

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

解题思路

要设计一个支持常数时间内获取最小元素的栈，我们可以使用两个栈：

主栈（stack）：用于存储所有元素，支持常规的栈操作。
最小栈（minStack）：用于存储当前主栈中每个状态下的最小值。

关键操作

push 操作：
- 将元素推入主栈。
- 如果最小栈为空，或者新元素小于等于最小栈的栈顶元素，则将该元素也推入最小栈。
pop 操作：
- 弹出主栈的栈顶元素。
- 如果弹出的元素等于最小栈的栈顶元素，则同时弹出最小栈的栈顶元素（表示当前最小值已从主栈移除）。
top 操作：直接返回主栈的栈顶元素。
getMin 操作：直接返回最小栈的栈顶元素（即当前栈中的最小元素）。

为什么使用“小于等于”？

当新元素等于最小栈的栈顶元素时，也需要将其推入最小栈。这样可以确保当多个相同的最小值存在时，最小栈中也有多个相同的值，避免在 pop 操作时提前将最小值移除。

代码实现

import java.util.LinkedList;

class MinStack {
    // 注意不要使用 Stack 类，因为它继承自 Vector，是同步的，会导致一些性能问题
    private LinkedList<Integer> stack;    // 主栈
    private LinkedList<Integer> minStack; // 最小栈

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }
    
    public void push(int val) {
        stack.push(val);
        // 如果最小栈为空，或者新元素小于等于最小栈栈顶元素，则推入最小栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        int popVal = stack.pop();
        // 如果弹出的元素等于最小栈栈顶元素，则同时弹出最小栈栈顶元素
        if (popVal == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

复杂度分析

时间复杂度：
- push：O(1)，每次操作只涉及常数次栈操作。
- pop：O(1)，每次操作只涉及常数次栈操作。
- top：O(1)，直接返回主栈栈顶元素。
- getMin：O(1)，直接返回最小栈栈顶元素。
空间复杂度：O(n)，最坏情况下需要两个栈存储所有元素，但最小栈在优化后通常存储元素较少。

总结

通过使用两个栈（主栈和最小栈），我们可以在常数时间内完成所有栈操作并获取当前栈中的最小元素。最小栈的维护确保了在每次操作后都能快速获取到最小值，而主栈则负责常规的栈功能。这种方法既高效又易于实现，是解决此类问题的经典方案。

来源

155. 最小栈 | 力扣（LeetCode）

笑话人生

双栈结构实现最小栈功能：同步记录最小值（LeetCode 155）