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.
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: /** initialize your data structure here. */ MinStack() { } void push(int x) { m.push(x); if (h.size() == 0 || h.top() >= x) { h.push(x); } else { h.push(h.top()); } } void pop() { m.pop(); h.pop(); } int top() { return m.top(); } int getMin() { return h.top(); } private: stack<int> m; stack<int> h; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */解析：以上解法用了一个辅助栈，还可以不使用辅助栈，用一个变量来存储最小值。min_val来记录当前最小值，初始化为整型最大值，然后如果需要进栈的数字小于等于当前最小值min_val，那么将min_val压入栈，
并且将min_val更新为当前数字。在出栈操作时，先将栈顶元素移出栈，再判断该元素是否和min_val相等，相等的话我们将min_val更新为新栈顶元素，再将新栈顶元素移出栈即可。
转载于:https://www.cnblogs.com/simplepaul/p/11386260.html
相关资源：JAVA上百实例源码以及开源项目