剑指 Offer 30: 包含min函数的栈

[songyy5517]

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

分析 这道题的考点是栈，我们需要求每个状态下栈中的最小值。根据之前求队列最小值的题，我们可以确定需要定义两个数据结构，一个用于存放新增的元素，一个用于存放当前的最小值。因此，我们需要定义两个栈s1和s2。当添加元素时，首先将该元素添加至s1中，若当前元素小于s2栈顶元素，则将该元素添加至s2中。

[songyy5517]

思路：定义两个栈，主栈用于存放元素，辅助栈用于存放对应元素下的最小值

1. 定义两个属性 main_stack, aux_stack
2. 初始化
3. push方法：判断主栈是否为空，
   • 若为空，则将新元素加到主栈和辅助栈中；
   • 若不为空，则比较新元素和辅助栈的栈顶元素，将较小值加入辅助栈，新元素加入主栈。
4. pop方法：将主栈和辅助栈的栈顶元素都弹出
5. top方法：返回主栈的栈顶元素
6. min方法：返回辅助栈的栈顶元素

复杂度分析：

• 时间复杂度： $O(1)$ ，每个操作的时间复杂度都为 $O(1)$ 。
• 空间复杂度： $O(N)$ ，需要额外定义两个栈，每个栈的大小都为 $N$ 。

[songyy5517]

class MinStack {
    // 定义两个栈，一个为主栈用于存放数据，另一个为辅助栈用于存放对应元素下的最小值
    Stack<Integer> main_stack;
    Stack<Integer> aux_stack;

    /** initialize your data structure here. */
    public MinStack() {
        // 初始化
        main_stack = new Stack<Integer>();
        aux_stack = new Stack<Integer>();
    }

    public void push(int x) {
        // 若栈为空，则将元素添加至主栈和辅助栈
        if (aux_stack.isEmpty()){
            aux_stack.add(x);
        }

        // 若不为空，则比较新元素和辅助栈的栈顶元素，将较小者添加到辅助栈中
        else{
            int min = x < aux_stack.peek() ? x : aux_stack.peek();
            aux_stack.add(min);
        }

        // 新元素加入主栈中
        main_stack.add(x);
    }

    public void pop() {
        // 把两个栈的栈顶元素都弹出
        main_stack.pop();
        aux_stack.pop();
    }

    public int top() {
        // 返回主栈的栈顶元素
        return main_stack.peek();
    }

    public int min() {
        // 返回辅助栈的栈顶元素
        return aux_stack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

[songyy5517]

2023/2/25 2023/3/6 2023/12/12

• 判断栈中元素相等：equals而不是==