关于栈中最小元素O(1)

1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。

　　算法思想：需要设计一个辅助栈，用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置，虽然能节省空间，这其实是不对的，因为我在调用Min函数的时候，只能得到位置，还要对存储元素的栈不断的pop，才能得到最小值——时间复杂度o(1)。

　　所以，还是在辅助栈中存储元素吧。

　　此外，还要额外注意Push操作，第一个元素不用比较，自动成为最小值入栈。其它元素每次都要和栈顶元素比较，小的那个放到栈顶。

public　class　NewStack
{
　　　　private　Stack　dataStack;
　　　　private　Stack　mindataStack;
　　　　public　NewStack()
　　　　{
　　　　　　　　dataStack　=　new　Stack();
　　　　　　　　mindataStack　=　new　Stack();
　　　　}
　　　　public　void　Push(int　element)
　　　　{
　　　　　　　　dataStack.Push(element);
　　　　　　　　if　(mindataStack.Count　==　0)
　　　　　　　　　　　　mindataStack.Push(element);
　　　　　　　　else　if　(element　<=　(int)mindataStack.Peek())
　　　　　　　　　　　　mindataStack.Push(element);
　　　　　　　　else　//(element　>　mindataStack.Peek)
　　　　　　　　　　　　mindataStack.Push(mindataStack.Peek());
　　　　}
　　　　
　　　　public　int　Pop()
　　　　{
　　　　　　　　if　(dataStack.Count　==　0)
　　　　　　　　　　　　throw　new　Exception("The　stack　is　empty");
　　　　　　　　
　　　　　　　　mindataStack.Pop();
　　　　　　　　return　(int)dataStack.Pop();
　　　　}
　　　　public　int　Min()
　　　　{
　　　　　　　　if　(dataStack.Count　==　0)
　　　　　　　　　　　　throw　new　Exception("The　stack　is　empty");
　　　　　　　　
　　　　　　　　return　(int)mindataStack.Peek();
　　　　}
}

　　2.设计含min函数的栈的另解

　　话说，和青菜脸呆久了，就沾染了上海小市民意识，再加上原本我就很抠门儿，于是对于上一题目，我把一个栈当成两个用，就是说，每次push，先入站当前元素，然后入栈当前栈中最小元素；pop则每次弹出2个元素。

　　算法代码如下所示（这里最小元素位于当前元素之上，为了下次比较方便）：

public　class　NewStack
{
　　　　private　Stack　stack;
　　　　public　NewStack()
　　　　{
　　　　　　　　stack　=　new　Stack();
　　　　}
　　　　public　void　Push(int　element)
　　　　{
　　　　　　　　if　(stack.Count　==　0)
　　　　　　　　{
　　　　　　　　　　　　stack.Push(element);
　　　　　　　　　　　　stack.Push(element);
　　　　　　　　}
　　　　　　　　else　if　(element　<=　(int)stack.Peek())
　　　　　　　　{
　　　　　　　　　　　　stack.Push(element);
　　　　　　　　　　　　stack.Push(element);
　　　　　　　　}
　　　　　　　　else　//(element　>　stack.Peek)
　　　　　　　　{
　　　　　　　　　　　　object　min　=　stack.Peek();
　　　　　　　　　　　　stack.Push(element);
　　　　　　　　　　　　stack.Push(min);　　　　　　　　　　　　
　　　　　　　　}
　　　　}
　　　　public　int　Pop()
　　　　{
　　　　　　　　if　(stack.Count　==　0)
　　　　　　　　　　　　throw　new　Exception("The　stack　is　empty");
　　　　　　　　stack.Pop();
　　　　　　　　return　(int)stack.Pop();
　　　　}
　　　　public　int　Min()
　　　　{
　　　　　　　　if　(stack.Count　==　0)
　　　　　　　　　　　　throw　new　Exception("The　stack　is　empty");
　　　　　　　　return　(int)stack.Peek();
　　　　}
}

　　之所以说我这个算法比较叩门，是因为我只使用了一个栈，空间复杂度o(N)，节省了一半的空间（算法1的空间复杂度o(2N)）。