题目描述：

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

输入输出样例：

示例 1：
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

提示：
-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10⁴ 次

题解：

解题思路：

思路一（辅助栈）：

1、根据题目的要求，此问题需要对应入栈元素和当前元素存入栈时的最小值，这里不能用一个min变量来存储。因在出栈时，一个min变量不方便更新栈顶元素的最小值。所以我们采用一个额外的栈来存储当前栈中的最小值。
官方题解链接（讲解的还是不错的）

2、复杂度分析：
① 时间复杂度：O(1)。插入、删除与读取操作都是 O(1)。
② 空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

代码实现

代码实现（思路一（辅助栈））：

class MinStack {private:stack<int> val_stack;  // 用于存储栈中的所有元素stack<int> min_stack;  // 用于存储每次压入元素后的最小值public:// 构造函数，初始化时将最小栈设置为一个非常大的值（为了统一入栈操作）MinStack() {min_stack.emplace(INT_MAX);  // 设置一个非常大的初始值作为最小值}// 将元素压入栈中，并更新最小栈（每一个值对应一个压入栈中的最小值）void push(int val) {val_stack.emplace(val);  // 将元素压入值栈// 更新最小栈，最小栈的栈顶为当前值和之前栈顶最小值中的较小值min_stack.emplace(min(min_stack.top(), val));  }// 弹出栈顶元素，并更新最小栈void pop() {val_stack.pop();  // 弹出值栈的栈顶元素min_stack.pop();  // 弹出最小栈的栈顶元素}// 获取栈顶元素int top() {return val_stack.top();  // 返回值栈的栈顶元素}// 获取当前栈中的最小值int getMin() {return min_stack.top();  // 返回最小栈的栈顶元素，即当前栈中的最小值}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
#include <stack>
using namespace std;class MinStack {private:stack<int> val_stack;  // 用于存储栈中的所有元素stack<int> min_stack;  // 用于存储每次压入元素后的最小值public:// 构造函数，初始化时将最小栈设置为一个非常大的值（为了统一入栈操作）MinStack() {min_stack.emplace(INT_MAX);  // 设置一个非常大的初始值作为最小值}// 将元素压入栈中，并更新最小栈（每一个值对应一个压入栈中的最小值）void push(int val) {val_stack.emplace(val);  // 将元素压入值栈// 更新最小栈，最小栈的栈顶为当前值和之前栈顶最小值中的较小值min_stack.emplace(min(min_stack.top(), val));  }// 弹出栈顶元素，并更新最小栈void pop() {val_stack.pop();  // 弹出值栈的栈顶元素min_stack.pop();  // 弹出最小栈的栈顶元素}// 获取栈顶元素int top() {return val_stack.top();  // 返回值栈的栈顶元素}// 获取当前栈中的最小值int getMin() {return min_stack.top();  // 返回最小栈的栈顶元素，即当前栈中的最小值}
};int main(int argc, char const *argv[])
{MinStack minStack  ;minStack .push(-2);minStack .push(0);minStack .push(-3);cout<<minStack.getMin()<<endl;      // --> 返回 -3.minStack.pop();cout<<minStack.top()<<endl;         //--> 返回 0.cout<<minStack.getMin()<<endl;     //--> 返回 -2.return 0;
}

部分代码解读

栈中的push和emplace对比

stack<int> val_stack;
val_stack.emplace(val);
val_stack.push(val);

push 会通过拷贝或移动操作将元素压入栈。
emplace 会在栈内部直接构造元素，通常能避免不必要的拷贝或移动操作。可以避免不必要的拷贝或移动，效率上会有所提升。

LeetCode 热题 100_最小栈（70_155)原题链接
欢迎大家和我沟通交流(✿◠‿◠)