[数据结构与算法]leetcode155. 最小栈

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

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

提示： pop、top和getMin操作总是在非空栈是调用。

示例：
?输入：[“MinStack”, “push”, “push”, “push”, “getMin”, “pop”, “top”, “getMin”]
????[[ ], [-2], [0], [-3], [ ], [ ], [ ], [ ]]
?输出：[null, null, null, null, -3, null, 0, -2]

思路一：
使用两个栈，一个栈用于存储数据（数据栈），另一个栈用于存储数据栈对应位置向下的最小值（最小栈）。
例如，-2入栈时栈为空，则该位置向下的最小值就是-2本身，于是-2入最小栈；接着0入栈，该位置向下的最小值是-2，则-2继续入最小栈；最后-3入栈，该位置向下的最小值就是-3了，则将-3入最小栈。若是数据栈需要出栈，则最小栈也跟着进行出栈操作。

这样一来，无论什么时候，最小栈的栈顶元素都是数据栈中的最小元素。

代码如下：

class MinStack {
public:
	/** initialize your data structure here. */
	MinStack() {
		//构造函数无需编写，使用默认构造函数即可
	}

	void push(int val) {
		_st.push(val); //将val压入数据栈
		if (_minst.empty() || val < _minst.top()) //若val比最小栈的栈顶元素小，则将val压入最小栈
		{
			_minst.push(val);
		}
		else //若val比最小栈的栈顶元素大，则将最小栈栈顶元素压入最小栈
		{
			_minst.push(_minst.top());
		}
	}

	void pop() {
		_st.pop(); //数据栈进行pop
		_minst.pop(); //最小栈进行pop
	}

	int top() {
		return _st.top(); //返回数据栈栈顶元素
	}

	int getMin() {
		return _minst.top(); //返回最小栈栈顶元素
	}
private:
	stack<int> _st; //数据栈
	stack<int> _minst; //最小栈
};

/**
 1. Your MinStack object will be instantiated and called as such:
 2. MinStack* obj = new MinStack();
 3. obj->push(val);
 4. obj->pop();
 5. int param_3 = obj->top();
 6. int param_4 = obj->getMin();
*/

思路二：
实际上我们可以发现，如果入栈数据当中存在大量连续数据都比已经入栈的数据要小，按照思路一的方法进行操作，则最小栈当中就会出现许多连续且相同的数据。

为了解决这个问题，我们可以改变最小栈的入栈规则：

1. 若最小栈为空，则数据栈入数据，最小栈也跟着入数据。
2. 若压入数据栈的数据比最小栈栈顶的元素大，则最小栈不进行任何操作。
3. 若压入数据栈的数据比最小栈栈顶的元素小或是相等，则最小栈也跟着数据栈入数据。

当然，我们也需要重新制定最小栈的出栈规则：

1. 若数据栈出栈数据与最小栈栈顶元素相等，则最小栈也跟着出栈。
2. 若数据栈出栈数据与最小栈栈顶元素不同，则最小栈不进行任何操作。

代码如下：

class MinStack {
public:
	/** initialize your data structure here. */
	MinStack() {
		//构造函数无需编写，使用默认构造函数即可
	}

	void push(int val) {
		_st.push(val); //将val压入数据栈
		if (_minst.empty() || val <= _minst.top()) //最小栈为空或val小于等于最小栈栈顶元素
		{
			_minst.push(val); //最小栈也跟着数据栈入数据
		}
	}

	void pop() {
		if (_minst.top() == _st.top()) //最小栈与数据栈栈顶元素相同
		{
			_minst.pop(); //最小栈也跟着出栈
		}
		_st.pop(); //数据栈出栈
	}

	int top() {
		return _st.top(); //返回数据栈栈顶元素
	}

	int getMin() {
		return _minst.top(); //返回最小栈栈顶元素
	}
private:
	stack<int> _st; //数据栈
	stack<int> _minst; //最小栈
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/