剑指offer - 包含min函数的栈

题目链接:包含min函数的栈

首先考虑时间复杂度，压栈、弹出、取min都要求O(1)的复杂度。而对n个数据取min，要想达到插入和取min都O(1)，说明是通过时间换空间的方法。
因为要实现栈的压入弹出，所以栈结构是必须的。除此之外，通过什么数据结构，能辅助O(1)的时间复杂度下可以拿到min。说明需要把每个位置对应的min存下来。而且插入数据时也要O(1)说明不是通过排序的方法来获取min的，否则插入数据至少要O(nlogn)。
因此可以想到，可以记录每个数据压栈时对应的min，在一个辅助栈中，辅助栈随原栈一起压入和弹出。
辅助栈法解决思路：除了数据栈，创建一个辅助栈，存对应数据压栈时当前栈内的min数据。方法就是数据压栈时比较，若当前数据比min栈顶大，说明当前数据压栈后，min还是当前的栈顶，继续压入存个min就可以了。如果当前数据比min栈顶小，说明这个数据压栈后，当前数据栈的min变为该数据，因此min栈压入该数据。

class Solution {
private:stack<int> min_s;stack<int> s;
public:void push(int value) {s.push(value);if (min_s.empty() || min_s.top() >= value) {min_s.push(value);} else {min_s.push(min_s.top());}}void pop() {s.pop();min_s.pop();}int top() {return s.top();}int min() {return min_s.top();}
};