LeetCode155 最小栈

LeetCode 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.

想了一下，这个题目可以用两个栈来实现，一个栈储存正常的数据，另一个栈储存当前的最小值。需要返回最小值的时候直接返回最小栈的栈顶元素即可。弹出栈的时候也是同样的道理。 最后代码如下：

class MinStack {
public:
	/** initialize your data structure here. */
	MinStack() {

	}

	void push(int x) {
		s.push(x);
		if (min_s.empty())
		{
			min_s.push(x);
		}
		else
		{
			if (x<min_s.top())
			{
				min_s.push(x);
			}
			else
			{
				min_s.push(min_s.top());
			}
		}
	}

	void pop() {
		s.pop();
		min_s.pop();
	}

	int top() {
		return s.top();
	}

	int getMin() {
		return min_s.top();
	}
private:
	stack<int> s;
	stack<int> min_s;
};

看到网上别人的解法也很神奇，可以不用两个栈就可以实现该算法，可以用一个栈的两个数据位来保存数据，一个数据保存真正 push 进来的值，另一个数据保存当前的最小值，不过实际原理和用两个栈来实现么什么区别。