您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
题目:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
思路一:
通过每次在压入栈顶的元素与当前最小元素相比后,保存一遍最小元素,每次弹出,都弹出两个,这个就能得到栈当前最小元素了
代码:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); int min=value; s1.push(min); } else { int min=s1.top(); if(value<min) { min=value; } s1.push(value); s1.push(min); } } //弹出两次 void pop() { int min=s1.top(); s1.pop(); int val=s1.top(); s1.pop(); } int top(){ int min=s1.top(); s1.pop(); int val=s1.top(); s1.push(min); return val; } int min() { return s1.top(); } private: stack<int> s1; };
思路二:利用两个栈,一个栈用于压入数据,另一个栈用于压入数据时的最小元素。无论最小元素是不是压栈的元素,都保存到第二个栈中
代码:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); s2.push(value); } else { s1.push(value); int min=s2.top(); if(min>value) { s2.push(value); } else { s2.push(min); } } } void pop() { if(!s1.empty()) { s1.pop(); s2.pop(); } } int top() { return s1.top(); } int min() { return s2.top(); } private: stack<int> s1,s2; };
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。