当前位置： 面试刷题>> 最小栈(经典算法150题)
### 题目描述
**最小栈**
设计一个支持 `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 示例代码
```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 示例代码
```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 示例代码
```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`）来高效地实现获取栈中最小元素的功能。