首页 > 代码库 > leetcode[155] Min Stack
leetcode[155] Min Stack
实现一个堆，可以push，pop，top，和getMin
主要的应该是getMin，如何找到最小的数。如果每次要找最小的数遍历一边，那貌似没什么意义了。
做法是，用两个堆，一个用来正常的操作，另一个是记录到当前最小值，如果来一个数字，比最小值的那个对的top还小那就，两个堆都要push，如果pop的时候pop的数和最小值的那个堆的top一样，那就最小值的那个堆也要pop。在getMin的时候，只要返回最小值那个堆的top就可以了。
稍微模拟一下几个数字进出堆就知道了。
class MinStack {public: stack<int> sta, minsta; void push(int x) { sta.push(x); if (minsta.empty() || x <= minsta.top()) minsta.push(x); } void pop() { if (!minsta.empty() && minsta.top() == sta.top()) minsta.pop(); sta.pop(); } int top() { return sta.top(); } int getMin() { return minsta.top(); }};
leetcode[155] Min Stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。