首页 > 剑指offer > 包含min函数的栈-剑指offer
2014
07-23

包含min函数的栈-剑指offer

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

分析:google的一道面试题。我看到这道题目时,第一反应就是每次push一个新元素时,将栈里所有逆序元素排序。这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈,这种思路设计的数据结构已经不是一个栈了。

在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次push一个新元素进栈的时候,如果该元素比当前的最小元素还要小,则更新最小元素。

乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被pop出去,如何才能得到下一个最小元素?

注意读题:对空间复杂的没有特别的要求,完全可以借助辅助空间

因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈。每次push一个新元素的时候,同时将最小元素(或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构,用最小元素的位置将能减少空间消耗)push到辅助栈中;每次pop一个元素出栈的时候,同时pop辅助栈。

Java代码如下:

public class MinStack<T> {
	private Stack<T> data;
	private Stack<T> minStack;

	public MinStack(){
		data = new Stack();
		minStack = new Stack();
	}

	public T min(){
		return minStack.peek();
	}

	public T pop(){
		minStack.pop();
		return data.pop();
	}

	public void push(T t){
		if(data.size() == 0 ){
			minStack.push(t);
		}else{
			T minValue = min();
			if(( (Comparable) t ).compareTo( minValue ) < 0)
				minStack.push(t);
			else
				minStack.push(minValue);
		}
		data.push(t);
	}

	public static void main(String[] args) {
		MinStack<Integer> ms = new MinStack<Integer>();
		ms.push(4);;
		ms.push(3);
		ms.push(2);
		ms.push(5);
		ms.push(1); 
		System.out.println("min:" + ms.min() + "  pop:" +ms.pop() );
		System.out.println("min:" + ms.min() + "  pop:" +ms.pop() );		
		System.out.println("min:" + ms.min() + "  pop:" +ms.pop() );		
		System.out.println("min:" + ms.min() + "  pop:" +ms.pop() );

	}
}

参考:http://zhedahht.blog.163.com/blog/static/25411174200712895228171/


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?