免费招聘网站推荐,深圳网站优化最好的方法,长沙网页设计培训机构,wordpress转微信文章目录 Tag题目来源题目解读解题思路方法一#xff1a;辅助栈方法二#xff1a;一个栈方法三#xff1a;栈中存放差值 其他语言python3 写在最后 Tag
【设计类】【栈】 题目来源
155. 最小栈 题目解读
本题是一个设计类的题目#xff0c;设计一个最小栈类 MinStack() … 文章目录 Tag题目来源题目解读解题思路方法一辅助栈方法二一个栈方法三栈中存放差值 其他语言python3 写在最后 Tag
【设计类】【栈】 题目来源
155. 最小栈 题目解读
本题是一个设计类的题目设计一个最小栈类 MinStack() 实现
MinStack()初始化堆栈对象void push(int val)将元素val推入堆栈void pop()删除堆栈顶部的元素int top()获取堆栈顶部的元素int getMin()获取堆栈中的最小元素。 解题思路
方法一辅助栈
维护两个栈一个栈就是常规的栈 stk1另一个栈 stk2 用来存放已经插入栈 stk1 中数字的最小值。 注意入栈和出栈操作时两个栈都要更新。 实现代码
class MinStack {public:MinStack() {min_stk.push(INT_MAX);}void push(int val) {stk.push(val);min_stk.push(std::min(min_stk.top(), val));}void pop() {stk.pop();min_stk.pop();}int top() {return stk.top();}int getMin() {return min_stk.top();}private:std::stackint stk;std::stackint min_stk;
};/*** 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 ) O(1) O(1)。
空间复杂度 O ( n ) O(n) O(n) n n n 为 操作次数。
方法二一个栈
可以只使用一个栈来同时保存当前的最小值和 val。
实现代码
class MinStack {
private:stackpairint, int stk;
public:MinStack() {stk.push(make_pair(INT_MAX, INT_MAX));}void push(int val) {stk.push({min(stk.top().first, val), val});}void pop() {stk.pop();}int top() {return stk.top().second;}int getMin() {return stk.top().first;}
};/*** 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 ) O(1) O(1)。
空间复杂度 O ( 1 ) O(1) O(1)。
方法三栈中存放差值
现在我们维护一个变量 minVal表示当前插入的变量的最小值栈中每次入栈的是 val 与 minVal 的差值 differ。现在进行具体分析
push(int val)如果此时栈为空我们更新 minVal val向栈中插入 0如果此时栈非空首先向栈中插入 diff根据 diff 的值来更新 minVal 如果 diff 0说明插入的 val 大于当前的 minVal则 minVal 不需要更新否则表明插入的 val 小于或者等于当前的 minVal则更新 minVal val。 pop()我们需要根据 diff 来更新弹出栈顶元素后的 minVal具体地 先弹出栈顶元素 diff并 pop如果 diff 0说明我们当时插入的 val 大于当时的 minVal则 minVal 是不需要更新的否则说明当时插入的 val 小于或者等于 minVal当时的 minVal 是插入的 val需要将 minVal 还原回去即当时插入 val 更新 minVal 的过程如下还原回去得到 minVal minVal diff。 d i f f v a l − m i n V a l ; m i n V a l v a l ; diff val - minVal; minVal val; diffval−minVal;minValval;
top()如果 diff 0表示 minVal 就是最小栈的栈顶元素否则 minVal diff 才是最小栈的栈顶元素。getMin()直接返回 minVal 即可。
实现代码
class MinStack {
private:stacklong long stk;long long minVal, diff;
public:MinStack() {}void push(int val) {if (stk.empty()) {stk.push(0);minVal val;}else {diff val - minVal;stk.push(diff);minVal diff 0 ? minVal : val;}}void pop() {diff stk.top();stk.pop();if (diff 0) {minVal minVal - diff;}}int top() {return stk.top() 0 ? minVal : minVal stk.top();}int getMin() {return 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();*/复杂度分析
时间复杂度 O ( 1 ) O(1) O(1)。
空间复杂度 O ( 1 ) O(1) O(1)。 其他语言
python3
以下只给出方法三的 python3 代码该方法比较巧妙值得好好研究。
class MinStack:def __init__(self):initialize your data structure here.self.stack []def push(self, x: int) - None:if not self.stack:self.stack.append(0)self.min_value xelse:diff x-self.min_valueself.stack.append(diff)self.min_value self.min_value if diff 0 else xdef pop(self) - None:if self.stack:diff self.stack.pop()if diff 0:self.min_value self.min_value - diffdef top(self) - int:return self.min_value if self.stack[-1] 0 else self.stack[-1] self.min_valuedef getMin(self) - int:return self.min_value if self.stack else -1写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
