155最小栈/c++
155. 最小栈 - 力扣（LeetCode）
设计一个支持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.
题解1
struct 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 { stack<int> x_stack; stack<int> 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(); } };