LeetCode怎样实现包含min函数的栈

问题描述

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

解决思路

首先，我们需要一个普通的栈来支持 push，pop，top 操作。接下来，我们需要维护一个辅助栈来存储当前栈中的最小元素。

辅助栈的作用是在普通栈发生 push 或者 pop 操作时，能够实时更新当前最小元素。

解决方案

1. 初始化：我们需要创建两个栈，一个是普通栈，另一个是辅助栈。开始时，两个栈都为空。

2. push操作：当执行 push 操作时，我们首先将元素加入到普通栈中。然后，我们需要判断当前辅助栈是否为空，或者当前元素是否小于等于辅助栈的栈顶元素。如果是的话，我们将当前元素也加入到辅助栈中；否则，我们将辅助栈的栈顶元素再次加入到辅助栈中。

3. pop操作：当执行 pop 操作时，我们首先从普通栈中将元素删除。然后，我们从辅助栈中也删除一个元素。

4. top操作：当执行 top 操作时，我们直接返回普通栈的栈顶元素即可。

5. getMin操作：当执行 getMin 操作时，我们直接返回辅助栈的栈顶元素即可，该元素即为当前栈中的最小元素。

以下是包含min函数的栈的实现代码：

class MinStack {
       Stack stack;
    Stack minStack;
       
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
       
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }
       
    public void pop() {
        stack.pop();
        minStack.pop();
    }
       
    public int top() {
        return stack.peek();
    }
       
    public int getMin() {
        return minStack.peek();
    }
}

解决复杂度

该解决方案的时间复杂度为O(1)，空间复杂度为O(n)。

其中，push、pop、top和getMin操作的时间复杂度都为O(1)，因为在执行这些操作时只需要对栈进行相应操作，而不需要遍历整个栈。

辅助栈的空间复杂度为O(n)，因为在最坏情况下，辅助栈的元素个数和普通栈的元素个数一样。