esign 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.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
class MinStack { public: vector<int> a; vector<int> min; MinStack() { min.push_back(2147483647); } void push(int x) { a.push_back(x); min.push_back(x < min.back() ? x : min.back()); } void pop() { a.pop_back(); min.pop_back(); } int top() { return a.back(); } int getMin() { return min.back(); } }; class MinStack { public: stack<int> st; stack<int> nextMin; void push(int x) { if(st.empty()){ nextMin.push(x); }else if(nextMin.top() >= x){ nextMin.push(x); } st.push(x); } void pop() { int tmp = st.top(); st.pop(); if(tmp == nextMin.top()){ nextMin.pop(); } } int top() { return st.top(); } int getMin() { return nextMin.top(); } };
