题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
在该栈中，调用min，push，pop的时间复杂度都是O(1)
思路：
1、除了原来的栈s，增加一个辅助栈s_min，用来保存每次进栈时的最小元素。
Push操作：
栈s：元素value直接进栈s；
栈s_min：判断s_min是否为空或者value是否小于s_min的栈顶元素，如果是，将value压入栈s_min，否则将s_min.top()压入栈s_min；
Pop操作：
栈s：s.pop()；
栈s_min：s_min.pop()；
Min操作：
return s_min.top()；
2、思路1有个缺点就是如果每次进栈的元素都比原来最小元素大，那么栈中会重复记录相同的数字，这样大大浪费了存储空间。因此，我们可以只记录一个：
push操作：
栈s：元素value直接进栈s；
栈s_min：判断s_min是否为空或者value是否小于s_min的栈顶元素，如果是，将value压入栈s_min，否则不作为。
pop操作：
栈s：s.pop()；
栈s_min：如果s.top()等于s_min.top()，则s_min.pop()，否则不作为；
Min操作：
return s_min.top()；
缺点：当入栈存在重复元素时，在s_min的pop操作时会出现问题，这时需要在s_min中的每个最小值元素添加一个计数器，当计数器为0时，才进行pop操作。
代码：
这里只贴出思路1的实现代码。
template<typename T>
class StackWithMin{
public:
void push(const T& value);
void pop();
const T& min() const;
private:
stack<T> s;
stack<T> s_min;
}; template<typename T>
void StackWithMin<T>::push(const T& value){
s.push(value);
if(s_min.empty() || value<s_min.top())
s_min.push(value);
else
s_min.push(s_min.top());
} template<typename T>
void StackWithMin<T>::pop(){
assert(!s.empty() && !s.empty());
s.pop();
s_min.pop();
} template<typename T>
const T& StackWithMin<T>::min() const{
assert(!s.empty() && !s.empty());
return s_min.top();
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/4c776177d2c04c2494f2555c9fcc1e49?rp=1
AC代码：
class Solution {
public:
void push(int value) {
s.push(value);
if(s_min.empty() || value<s_min.top())
s_min.push(value);
else
s_min.push(s_min.top());
}
void pop() {
s.pop();
s_min.pop();
}
int top() {
return s.top();
}
int min() {
return s_min.top();
}
private:
stack<int> s;
stack<int> s_min;
};