最小栈
题目要求
设计一个栈，这个栈除了能够进行常规的压栈（push）、出栈（pop）、获取栈顶元素（top）操作外，还能够在常数时间内检索到栈中的最小元素。具体来说，需要实现以下功能：
MinStack()：构造一个新的最小栈。void push(int val)：将元素val压入栈中。void pop()：移除栈顶元素。int top()：返回栈顶元素。int getMin()：检索栈中的最小元素。
解题思路
为了在常数时间内检索到最小元素，我们需要在每个元素入栈时记录下当前栈的最小值。这意味着每个元素都需要携带一个额外的信息，即入栈时栈内的最小值。
这可以通过以下方式实现：
- 使用两个栈，一个用来存储所有的元素（我们称之为主栈），另一个用来存储每个状态下的最小值（我们称之为辅助栈）。
- 当一个元素要入栈时，我们将其压入主栈，并比较此元素与辅助栈的栈顶元素（当前的最小值）。如果辅助栈为空或者此元素更小，那么也将这个元素压入辅助栈。
- 当执行出栈操作时，同时从主栈和辅助栈中移除栈顶元素，但只有当两个栈顶元素相等时，才从辅助栈中移除元素，因为这表示移除的是当前的最小值。
- 获取栈顶元素时，直接返回主栈的栈顶元素。
- 获取最小元素时，返回辅助栈的栈顶元素，因为辅助栈的栈顶元素始终是当前栈中的最小值。
通过这种方式，我们可以确保push、pop、top和getMin操作的时间复杂度都是 O(1)。
Golang 版本
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
// 如果minStack为空或者val小于等于minStack的栈顶元素，则将val也推入minStack
if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
this.minStack = append(this.minStack, val)
}
}
func (this *MinStack) Pop() {
// 如果stack的栈顶元素等于minStack的栈顶元素，则同时弹出
if this.stack[len(this.stack)-1] == this.minStack[len(this.minStack)-1] {
this.minStack = this.minStack[:len(this.minStack)-1]
}
this.stack = this.stack[:len(this.stack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack)-1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
这段代码定义了一个MinStack结构体，其中包含两个切片：stack用于存储所有元素，minStack用于存储每个状态下的最小值。Constructor函数初始化一个MinStack对象。Push、Pop、Top和GetMin方法分别实现了题目要求的功能。
C++版本
#include <stack>
using namespace std;
class MinStack {
private:
stack<int> s1; // 主栈，用于存储所有元素
stack<int> s2; // 辅助栈，用于存储每个状态下的最小值
public:
MinStack() {
}
void push(int val) {
s1.push(val);
// 如果s2为空或者val小于等于s2的栈顶元素，则将val也推入s2
if (s2.empty() || val <= s2.top()) {
s2.push(val);
}
}
void pop() {
// 如果s1的栈顶元素等于s2的栈顶元素，则同时弹出
if (s1.top() == s2.top()) {
s2.pop();
}
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
这段 C++代码定义了一个MinStack类，其中包含两个私有成员：s1和s2，分别是两个栈，用于实现题目要求的功能。push方法将元素压入s1，并在必要时将元素压入s2以跟踪最小值。pop方法从s1中弹出元素，并在弹出的元素是当前最小值时，也从s2中弹出。top方法返回s1的栈顶元素，而getMin方法返回s2的栈顶元素，即当前的最小值。
Python 版本
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
# 如果min_stack为空或者val小于等于min_stack的最后一个元素，则将val也添加到min_stack
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
# 如果stack的最后一个元素等于min_stack的最后一个元素，则同时移除
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
这段 Python 代码定义了一个MinStack类，其中包含两个列表：stack用于存储所有元素，min_stack用于存储每个状态下的最小值。__init__方法初始化一个MinStack对象。push、pop、top和getMin方法分别实现了题目要求的功能。
Java 版本
import java.util.Stack;
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
// 如果minStack为空或者val小于等于minStack的栈顶元素，则将val也推入minStack
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
// 如果stack的栈顶元素等于minStack的栈顶元素，则同时弹出
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
// Your MinStack object will be instantiated and called as such:
// MinStack obj = new MinStack();
// obj.push(val);
// obj.pop();
// int param_3 = obj.top();
// int param_4 = obj.getMin();
这段 Java 代码定义了一个MinStack类，其中包含两个Stack<Integer>类型的成员变量：stack用于存储所有元素，minStack用于存储每个状态下的最小值。MinStack构造函数初始化这两个栈。push方法将元素压入stack，并在必要时将元素压入minStack以跟踪最小值。pop方法从stack中弹出元素，并在弹出的元素是当前最小值时，也从minStack中弹出。top方法返回stack的栈顶元素，而getMin方法返回minStack的栈顶元素，即当前的最小值。
Rust 版本
struct MinStack { stack: Vec<i32>, min_stack: Vec<i32>, } impl MinStack { fn new() -> Self { MinStack { stack: Vec::new(), min_stack: Vec::new(), } } fn push(&mut self, val: i32) { self.stack.push(val); if self.min_stack.is_empty() || val <= *self.min_stack.last().unwrap() { self.min_stack.push(val); } } fn pop(&mut self) { if let Some(val) = self.stack.pop() { if val == *self.min_stack.last().unwrap() { self.min_stack.pop(); } } } fn top(&self) -> i32 { *self.stack.last().unwrap() } fn get_min(&self) -> i32 { *self.min_stack.last().unwrap() } } fn main() { let mut min_stack = MinStack::new(); min_stack.push(-2); min_stack.push(0); min_stack.push(-3); println!("Min: {}", min_stack.get_min()); // Returns -3. min_stack.pop(); println!("Top: {}", min_stack.top()); // Returns 0. println!("Min: {}", min_stack.get_min()); // Returns -2. }
这段 Rust 代码定义了一个MinStack结构体，其中包含两个字段：stack和min_stack，分别是两个动态数组，用于实现题目要求的功能。new函数用于创建一个新的MinStack实例。push、pop、top和get_min方法分别实现了题目要求的功能。main函数展示了如何使用MinStack。
总结
在上述的解法中，我们设计了一个特殊的栈结构，称为最小栈（MinStack），它能够在常数时间内检索到最小元素。无论是 Python、Java 还是 Rust 版本的实现，核心思想都是使用两个栈：
- 主栈（stack）：用于存储所有的元素。
- 辅助栈（min_stack 或 minStack）：用于存储当前栈中的最小元素。
每次元素入栈时，我们将元素推入主栈。同时，如果辅助栈为空或者入栈元素的值小于等于辅助栈的栈顶元素，我们也将这个元素推入辅助栈。这样，辅助栈的栈顶元素始终是当前栈中的最小值。
当元素出栈时，如果主栈的栈顶元素等于辅助栈的栈顶元素，我们同时将辅助栈的栈顶元素弹出。这保证了辅助栈的栈顶元素始终是当前栈中剩余元素的最小值。
top方法和getMin方法分别用于获取主栈的栈顶元素和辅助栈的栈顶元素，后者即为当前栈的最小值。
这种设计允许我们在 O(1)时间复杂度内完成push、pop、top和getMin操作，同时空间复杂度为 O(n)，因为我们为每个元素在辅助栈中也存储了一份数据。