首页 > 代码库 > careercup-栈与队列 3.2
careercup-栈与队列 3.2
3.2 请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)。
我们假设除了用一个栈s1来保存数据，还用另一个栈s2来保存这些非冗余最小值。那么， 当我们将数据压到要s1时，同时将它和s2的栈顶元素比较，如果不大于s2的栈顶元素， 那么将当前值也压入s2中。这样一来，s2中保存的就是一个阶段性最小值。 即s2中的每个值都是s1中栈底到达某个位置的最小值。那么，如果执行pop操作呢？ 执行pop操作除了将s1中的栈顶元素出栈，还要将它和s2中的栈顶元素比较，如果相等， 说明这个值是栈底到栈顶的最小值，而它出栈后，最小值就不再是它了。所以， s2也要将栈顶元素出栈，新的栈顶元素将对应s1剩下元素中新的最小值。
C++实现代码：
#include<iostream>#include<stack>using namespace std;class MinStack{private: stack<int> stack1; stack<int> stack2;public: void push(int x) { if(stack1.empty()) { stack1.push(x); stack2.push(x); } if(stack1.top()<x) stack2.push(x); else { stack1.push(x); stack2.push(x); } } void pop() { if(stack1.empty()) stack2.pop(); if(stack1.top()==stack2.top()) { stack1.pop(); stack2.pop(); } else stack2.pop(); } int top() { if(stack2.empty()) return 0; else return stack2.top(); } int getMin() { if(stack1.empty()) return 0; else return stack1.empty(); }};int main(){ MinStack mystack;//StackWithMin mystack; for(int i=0; i<20; ++i) mystack.push(i); cout<<mystack.getMin()<<" "<<mystack.top()<<endl; mystack.push(-100); mystack.push(-100); cout<<mystack.getMin()<<" "<<mystack.top()<<endl; mystack.pop(); cout<<mystack.getMin()<<" "<<mystack.top()<<endl; return 0;}
careercup-栈与队列 3.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。