【LeetCode刷题之路】leetcode155.最小栈

LeetCode刷题记录

• 🌐 我的博客主页：iiiiiankor
• 🎯 如果你觉得我的内容对你有帮助，不妨点个赞👍、留个评论✍，或者收藏⭐，让我们一起进步！
• 📝 专栏系列：LeetCode 刷题日志
• 🌱 文章内容来自我的学习与实践经验，如果你有任何想法或问题，欢迎随时在评论区交流讨论。让我们一起探索更多的可能！🚀

LeetCode 155最小栈

解法1：

为实现这些操作，我们可以使用两个栈：

主栈（stack）：用于存储所有的元素。
辅助栈（min_stack）：用于存储当前栈中的最小元素。

push(x)：
将元素 x 推入主栈 stack。
如果 min_stack 为空，或 x 小于等于 min_stack 的栈顶元素，则将 x 也推入 min_stack。
pop()：
从主栈 stack 中弹出栈顶元素。
如果弹出的元素等于 min_stack 的栈顶元素，则也从 min_stack 中弹出栈顶元素。
top()：
返回主栈 stack 的栈顶元素。
getMin()：
返回辅助栈 min_stack 的栈顶元素，即当前栈中的最小元素。

图解：


代码：

class MinStack {
public:MinStack() {}void push(int val) {st.push(val);if(minval.empty() || val <= minval.top()){minval.push(val);}}void pop() {//如果top大于此时的最小值，直接pop//如果小于等于，那么minval也要popif(st.top() > minval.top()){st.pop();}else{st.pop();minval.pop();}}int top() {return st.top();}int getMin() {return minval.top();}
private:stack<int> st;stack<int> minval;     //辅助栈
};/*** 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();*/

引用计数优化

如果存在大量的重复值，那么上面的方法显然效率变低了，同时需要维护大量的minst
此时可利用引用计数的思想进行优化，minst中不再存储一个int，而是存储一个结构体。结构体中包含：
1、最小值
2、 最小值个数

下面是图解：

struct minVal{int val;int valCount;minVal(int x):valCount(0),val(x){}
};
class MinStack {
public:
//初始化列表 会初始化自定义成员MinStack() {}void push(int val) {st.push(val);//如果小于min的栈顶元素，就pushif(min.empty() || val < min.top().val){min.push(minVal(val));min.top().valCount++;}//val等于min的topelse if(!min.empty() && val == min.top().val){min.top().valCount++;//计数+1}}void pop() {//如果stack的top 大于min的栈顶，直接删除if(st.top() > min.top().val){st.pop();}else if(st.top() == min.top().val){if(min.top().valCount > 1)//大于1 就--count  {min.top().valCount--;}else      // 等于1  就pop{min.pop();}st.pop();}}int top() {return st.top();}int getMin() {return min.top().val;}
private:stack<int> st;stack<minVal> min;     //辅助栈
};