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.
with two stacks
class MinStack { public: MinStack() { minElem = INT_MAX; } void push(int x) { st.push(x); if (x <= minElem) { minSt.push(x); minElem = x; } } void pop() { if (st.empty()) return; if (st.top() == minElem) { minSt.pop(); if (!minSt.empty()) { minElem = minSt.top(); }else { minElem = INT_MAX; } } st.pop(); } int top() { if (st.empty()) return -1; return st.top(); } int getMin() { return (int)minElem; } private: stack<int> st; stack<int> minSt; long minElem; };with one stack
class MinStack { public: MinStack() { minElem = INT_MAX; } void push(int x) { if (x <= minElem) { st.push(minElem); minElem = x; } st.push(x); } void pop() { if (st.empty()) return; if (st.top() == minElem) { st.pop(); if (!st.empty()) { minElem = st.top(); st.pop(); }else { minElem = INT_MAX; } }else st.pop(); } int top() { if (st.empty()) return -1; return st.top(); } int getMin() { return (int)minElem; } private: stack<int> st; long minElem; };
No comments:
Post a Comment