net快速建站,俄罗斯乌克兰最新消息,网站做多长时间才有流量,设计的商城网站建设最小栈 一、题目链接二、题目三、算法原理思路1#xff1a;用一个变量存储最小元素思路2#xff1a;双栈普通栈和最小栈 四、编写代码五、时间复杂度 一、题目链接
最小栈
二、题目 三、算法原理
栈用数组、链表实现都行#xff0c;最主要的就是在能在常数时间内检索到最… 最小栈 一、题目链接二、题目三、算法原理思路1用一个变量存储最小元素思路2双栈普通栈和最小栈 四、编写代码五、时间复杂度 一、题目链接
最小栈
二、题目 三、算法原理
栈用数组、链表实现都行最主要的就是在能在常数时间内检索到最小元素的栈说明getMin是O(1)的接口。
思路1用一个变量存储最小元素
用一个变量存储最小元素push一个值就比较一下并且要判断是否要更新最小元素。但是若更新后再pop一下就会出问题此时栈中最小元素也会发生改变那么怎么更新呢更新成什么数呢遍历一遍栈吗这样就是O(n)的接口了与O(1)不符。 思路2双栈普通栈和最小栈
采用双栈的方式来实现普通栈正常存取数据和最小栈。
最小栈若向普通栈中push的元素大于当前最小栈中的栈顶元素就不用往最小栈中push若向普通栈中push的元素小于等于当前最小栈中的栈顶元素或者最小栈为空就向最小栈中pushgetMin获取最小栈中的栈顶元素即可。 若再push一个与最小元素相等的元素那么最小栈中是否也要push呢—— 要。若没有push普通栈pop元素-1此时pop了最小元素要更新最小值最小栈也pop了此时最小值理应还是-1而不是1。所以push的元素比最小栈栈顶元素小或相等minst都要push这个元素。 当前栈中最小元素是-1若pop元素7后最小元素还是-1此时最小栈不用动。若再pop此时删除的元素与最小栈中的栈顶元素相等那么这时最小栈要pop这时getMin就是1 不需要写构造、析构、拷贝构造、赋值。类的两个成员变量是自定义类型的不写构造编译器自动生成的默认构造会自动调用两个成员变量的默认构造拷贝构造、析构、赋值同理。
private:stackint _st;stackint _minst;构造函数像这样啥也不写或直接为空都是可以的 因为显示写构造了编译器就不会生成默认构造了。显示写构造不管有没有写初始化列表一个类都有初始化列表的。没有显示写初始化列表且没有给缺省值对于自定义类型的成员会调用它的默认构造。
封装 封装的简单形态数据和方法放到类里面想被看到的封装成公有不想被看到的封装成私有。 另一层封装的体现无需关心比如说像这道题的栈的底层是怎么实现的就只管怎么用即可知道了功能直接调用对应的功能。
四、编写代码
class MinStack {
public:MinStack(){}void push(int val) {_st.push(val);if (_minst.empty() || val _minst.top()) _minst.push(val);}void pop() {if (_st.top() _minst.top()) _minst.pop();_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stackint _st;stackint _minst;
};/*** 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();*/五、时间复杂度
所有接口的时间复杂度都是O(1)。
