首页 > 代码库 > LeetCode Min Stack
LeetCode Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Show Tags
Have you met this question in a real interview?
Yes
No
Discuss
题意:写一个新的栈:支持入栈,出栈,得到栈顶,和得到此时栈最小的那个数
思路:前三个操作都可以用一个栈来实现,求最小的话就需要一个新的单调栈来维护了,这个新的单调栈需要注意的地方是:当原始的栈pop掉一个数的时候可能会影响到这个单调栈,只要判断此时pop掉的话,是不是单调栈的栈顶就能解决了,因为这个单调栈是原始栈的子集
class MinStack { public: void push(int x) { st.push(x); if (stm.empty() || stm.top() >= x) stm.push(x); } void pop() { int top = st.top(); st.pop(); if (top == stm.top()) stm.pop(); } int top() { return st.top(); } int getMin() { return stm.top(); } private: stack<int> st; stack<int> stm; };
LeetCode Min Stack
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。