Leetcode_155. 最小栈
✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++_OJ
小伞的主页：xiaosan_blog
最小栈
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.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在非空栈上调用push,pop,top, andgetMin最多被调用3 * 104次
解题思路：
由于取栈内最小值时，不能改变原有的栈，所以采用两个栈，一个为正常栈(stack<int> x_stack;),另一个为最小栈( stack<int> min_stack;)
去栈顶元素/取最小值
int top() { return x_stack.top(); }
int getMin() { return min_stack.top(); }
正常栈/最小栈的插入
void push(int val) {
x_stack.push(val); // 正常插入
min_stack.push(min(min_stack.top(), val));//每次插入最小值在最小栈里面
}
初始化堆栈对象
MinStack() { min_stack.push(INT_MAX); } // 插入一个最大值
由于每次插入最小值进入栈中，需要进行比较，所以需初始化一个最大值，那么每次插入都为最小值。
正常栈/最小栈的删除
void pop() {
x_stack.pop();
min_stack.pop();
}
//这是就有人提问：正常栈删除为最后进栈的元素，最小栈是否也满足这样
是的，但最小栈的删除的元素却不同，我们每次插入的值不是最小栈栈顶元素的值，就是最小值进栈，那么每次删除不是原最小栈栈顶的元素，就是新进栈的最小元素
插入(-2,-3,0,5,3,6,8,7) ,调试一下
正常栈插入
最小栈插入
由于后面的值都大于-3的值，所以最小栈的插入都为-3，仔细观察，我们发现一个规律，除去最小栈初始化的 INT_MAX，他们的个数是匹配的，如果我们一直pop，-3最后是同时被删除在栈中的
完整代码
class MinStack { stack<int> x_stack; stack<int> min_stack; public: MinStack() {min_stack.push(INT_MAX); } // 插入一个最大值 void push(int val) { x_stack.push(val); // 正常插入 min_stack.push(min(min_stack.top(), val)); // 插入最小值在小栈里面 } void pop() { x_stack.pop(); min_stack.pop(); } int top() { return x_stack.top(); } int getMin() { return min_stack.top(); } };