155. 最小栈 - 力扣LeetCode设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现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.题解1struct Node { int lastmin; int val; Node* next; // 构造函数可选但推荐 Node() : lastmin(0), val(0), next(nullptr) {} }; class MinStack { private: int min_val; // 避免与函数 min 冲突改名为 min_val Node* top_node; // 指向头节点哨兵节点 public: MinStack() { top_node new Node(); // 创建哨兵头节点 min_val INT_MAX; // 初始最小值设为最大更健壮 } void push(int val) { // 如果栈为空即第一个真实元素 if (top_node-next nullptr) { min_val val; } Node* node new Node(); node-val val; node-lastmin min_val; // 保存当前最小值用于 pop 时恢复 min_val std::min(min_val, val); // 更新全局最小值 node-next top_node-next; top_node-next node; } void pop() { if (top_node-next nullptr) return; // 安全检查 Node* node top_node-next; min_val node-lastmin; // 恢复上一个最小值 top_node-next node-next; delete node; // 释放内存 } int top() { return top_node-next-val; } int getMin() { return min_val; } // 可选析构函数防止内存泄漏 ~MinStack() { while (top_node ! nullptr) { Node* temp top_node; top_node top_node-next; delete temp; } } }; /** * 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(); */官方题解class MinStack { stackint x_stack; stackint min_stack; public: MinStack() { min_stack.push(INT_MAX); } void push(int x) { x_stack.push(x); min_stack.push(min(min_stack.top(), x)); } void pop() { x_stack.pop(); min_stack.pop(); } int top() { return x_stack.top(); } int getMin() { return min_stack.top(); } };