淄博网络公司做网站的电话,济南网站建设推荐企优互联不错,策划书模板,无锡外贸网站开发目录
一、前言
二、题目描述
三、解题方法 ⭐解题方法--1 ⭐解题方法--2
四、总结
五、共勉 一、前言 最小栈这道题#xff0c;可以说是--栈专题--#xff0c;比较经典的一道题#xff0c;也是在面试中频率较高的一道题目#xff0c;通常在面试中#xff0c;面试官可…目录
一、前言
二、题目描述
三、解题方法 ⭐解题方法--1 ⭐解题方法--2
四、总结
五、共勉 一、前言 最小栈这道题可以说是--栈专题--比较经典的一道题也是在面试中频率较高的一道题目通常在面试中面试官可能会要求我们写出多种解法来实现这道题目所以大家需要对这道题目非常熟悉哦 二、题目描述 设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。 三、解题方法 ⭐解题方法--1 使用两个栈一个栈用于存储数据数据栈另一个栈用于存储数据栈对应位置向下的最小值最小栈。 其中 数据栈为_st 最小栈为min_st 所有 要入栈的元素都要 进入 _st 栈中当 min_st 的栈为空 或者 入栈的元素比 min_st 的栈顶元素小或者等于的时候才能进入 min_st栈在删除栈顶元素时当栈顶元素 与 min_st栈顶元素相同时则min_st栈顶元素也删除。若元素不相同则min_st 的 栈顶元素不删除 例如 【5332461】 当 5 入栈时当前最小元素为5min_st 让 5 入栈 此时 min_st 中元素为【5】 当 3 入栈时当前最小元素为3min_st 让 3入栈 此时 min_st 中元素为【5、3】 当 3 入栈时当前最小元素为3min_st 让 3入栈 此时 min_st 中元素为【5、3、3】 当 2 入栈时当前最小元素为2min_st 让 2入栈 此时 min_st 中元素为【5、3、3、2】 当 4 入栈时当前最小元素为2min_st 不让 4 入栈 此时 min_st 中元素为【5、3、3、2】 当 6 入栈时当前最小元素为2min_st 不让 6 入栈 此时 min_st 中元素为【5、3、3、2】 当 6 入栈时当前最小元素为1min_st 让 1 入栈 此时 min_st 中元素为【5、3、3、2、1】 当前 取最小的元素就可以在 min_st 的栈顶就可取到啦删除也是同样的原理o! 代码
class MinStack {
public:MinStack() {// 类中 默认采用构造初始化}void push(int val) {// 入栈_st.push(val);if(min_st.empty() || valmin_st.top()){min_st.push(val);}}void pop() {// 出栈if(min_st.top() _st.top()){min_st.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return min_st.top();}// 自定义两个栈stackint _st; // 数据栈stackint min_st; // 最小栈 --- 辅助栈
}; ⭐解题方法--2 在解题方法--1中还会存在浪费空间。 例如{5322264111} 用优化题解1中的方法min_st{53222111}出现了重复的2和1。 如果出现极端情况出现了N个2那么在min_st中也要存入N个2浪费了大量的空间。 有什么方法解决这个问题吗 计数方法和计数排序一样的原理。 例如{5322264111} 用一个结构体来记录 struct val_count
{int _val;//记录最小值int _count://记录次数
};在min_st{{51}{31}{23}{13}}——前一个数字表示这个阶段的最小值后面的数字表示这个阶段最小值出现的次数。 直到_count减到0才删除min_stack的栈顶元素。
struct val_count
{int _val;int _count;
};
class MinStack {
public:MinStack() {}void push(int val) {st.push(val);if(min_stack.empty()||val(min_stack.top()._val)){val_count temp{val,1};min_stack.push(temp);}else{if(val(min_stack.top()._val))min_stack.top()._count;}}void pop() {if(st.top()min_stack.top()._val){min_stack.top()._count--;if(min_stack.top()._count0)min_stack.pop();}st.pop();}int top() {return st.top();}int getMin() {return min_stack.top()._val;}private:stackint st;stackval_count min_stack;
}; 四、总结 最后我们来总结一下本文所介绍的内容本文讲解来一道力扣中有关最小栈的题目这道题目是校招笔试面试中有关链表章节非常高频的一道题目大家下去一定要自己再画画图分析一下把这段代码逻辑自己实现一遍才能更好地掌握 五、共勉 以下就是我对 最小栈 的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对 栈专题 的理解请持续关注我哦
