155. 最小栈

题目描述：

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。pop() -- 删除栈顶的元素。top() -- 获取栈顶元素。getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

算法1：

使用两个栈

一个栈存放数据，另一个栈存放前栈中最小的数据

class MinStack { stack<int>st; stack<int>min_st; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { st.push(x); if(min_st.empty()) min_st.push(x); else { if(min_st.top() > x) min_st.push(x); else min_st.push(min_st.top()); } } void pop() { st.pop(); min_st.pop(); } int top() { return st.top(); } int getMin() { return min_st.top(); } }; /** * 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(); */

算法2：

就使用一个栈，但是可以每次保存数据类型为 pair<int,int> 。第一个为插入的数据，第二个为目前的最小值