题目描述

最小栈

设计一个支持 push、pop、top 操作以及获取当前栈中最小元素的 getMin 操作的栈。

• push(x)：将元素 x 压入栈中。
• pop()：移除栈顶元素，并返回该元素。
• top()：返回栈顶元素，但不移除它。
• getMin()：返回栈中的最小元素。

注意：

• 栈中的元素均为整数。
• 栈的操作数可能很大，因此 getMin 操作的时间复杂度应尽可能低。

示例

假设我们进行以下操作：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
print(minStack.getMin());   // 返回 -3
minStack.pop();
print(minStack.top());      // 返回 0
print(minStack.getMin());   // 返回 -2

PHP 示例代码

class MinStack {
    private $stack;
    private $minStack;

    function __construct() {
        $this->stack = array();
        $this->minStack = array();
    }

    function push($x) {
        array_push($this->stack, $x);
        if (empty($this->minStack) || $x <= end($this->minStack)) {
            array_push($this->minStack, $x);
        }
    }

    function pop() {
        $top = array_pop($this->stack);
        if ($top == end($this->minStack)) {
            array_pop($this->minStack);
        }
        return $top;
    }

    function top() {
        return end($this->stack);
    }

    function getMin() {
        return end($this->minStack);
    }
}

// 使用示例
$minStack = new MinStack();
$minStack->push(-2);
$minStack->push(0);
$minStack->push(-3);
echo $minStack->getMin(); // 输出: -3
$minStack->pop();
echo $minStack->top();    // 输出: 0
echo $minStack->getMin(); // 输出: -2

Python 示例代码

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minStack or x <= self.minStack[-1]:
            self.minStack.append(x)

    def pop(self) -> None:
        if self.stack and self.stack[-1] == self.minStack[-1]:
            self.minStack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def getMin(self) -> int:
        return self.minStack[-1] if self.minStack else None

# 使用示例
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin())  # 输出: -3
minStack.pop()
print(minStack.top())     # 输出: 0
print(minStack.getMin())  # 输出: -2

JavaScript 示例代码

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(x) {
        this.stack.push(x);
        if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(x);
        }
    }

    pop() {
        if (this.stack.pop() === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

// 使用示例
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin()); // 输出: -3
minStack.pop();
console.log(minStack.top());    // 输出: 0
console.log(minStack.getMin()); // 输出: -2

通过这些示例代码，你可以看到如何通过维护一个辅助栈（minStack）来高效地实现获取栈中最小元素的功能。