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: stackst; stack stm; };