腾讯微信面试题--实现时间复杂度为O(1)的栈

     昨天下去去面试微信实习，遇到这道算法题，当时被卡住，故今天把它写出来做下知识整理，

 

原题：实现一个栈，满足min()  pop()  push()方法的时间复杂度都为O(1).( min()返回栈中最小元素 )

 

     思路1：用一个变量minItem记录栈中的最小值，在push()中 每次加入一个item就跟minItem对比，item更小，只item赋给minItem，然后再min() 中直接return  minItem;

 

     这种思路没考虑在pop()过程中，对minItem的影响，当栈顶元素是minItem，执行pop() 后minItem就不知道指向谁了，因为栈只记录最小值而起，至于最小值之前那些大小关系都没记录

 

      正确思路：为了实现更低的时间复杂度，我们都会想到用空间去换时间，所有这里增加一个数组来nextMinItem[index] 元素大小关系。如果当前最小值是 对象 item1 当push进来的item2比 item1更小，且元素个数从原本的a增加到a+1 这时候我们用我们就应该把item2这个更小的item赋给minItem 然后用nextMinItem[a+1] = item1 来记录 item2 后面的次小值，这样一来当item2 这个栈顶被pop()掉的话，我们就可以minItem = nextMinItem[a+1]，来恢复minItem。

 

 

代码：

 

package 腾讯面试题;

public class Stack {
	private int itemCount = 0;
	private Item minItem = null;
	private Item[] nextMinItem;
	private Item stackTop = null;
	private int maxSize = 100;

	public Stack() {
		nextMinItem = new Item[maxSize];
	}

	class Item {
		int Data;
		Item nextItem;

		public Item(int data) {
			this.Data = data;
		}

	}

	public boolean push(Item item) {
		if (itemCount == maxSize) {
			System.out.println("栈已满");
			return false;
		}
		itemCount++;
		if (minItem == null) {
			minItem = item;
		} else {
			if (item.Data < minItem.Data) {
				nextMinItem[itemCount] = minItem;
				minItem = item;
			}
		}
		item.nextItem = stackTop;
		stackTop = item;
		
		return true;
	}

	public boolean pop() {
		if (itemCount == 0) {
			System.out.println("栈是空的，无法出栈");
			return false;
		}

		if (stackTop == minItem) {
			minItem = nextMinItem[itemCount];
		}
		stackTop = stackTop.nextItem;
		itemCount--;
		return true;

	}

	public Item min() {
		if (itemCount == 0) {
			System.out.println("栈是空的，无最小值");
			return null;
		}
		return minItem;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Stack stack = new Stack();
		stack.push(stack.new Item(5));
		System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.push(stack.new Item(4));
		System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.push(stack.new Item(3));
		System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.push(stack.new Item(2));
		System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.push(stack.new Item(1));
		System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.pop();
		System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.pop();
		System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.pop();
		System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.pop();
		System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);
		stack.pop();
		System.out.println("栈结构为：\n|____1_____|\n|____2_____|\n|____3_____|\n|____4_____|\n|____5_____|\n");

		
	}
}

 

 

运行结果：

 

push:min=5 itemCount=1
push:min=4 itemCount=2
push:min=3 itemCount=3
push:min=2 itemCount=4
push:min=1 itemCount=5
pop :min=2 itemCount=4
pop :min=3 itemCount=3
pop :min=4 itemCount=2
pop :min=5 itemCount=1
栈结构为：
|____1_____|
|____2_____|
|____3_____|
|____4_____|
|____5_____|

 

 

博友thihy的另一种方法：

把nextMinItem嵌入Node中，这样就不需要限制maxSize。

class Node{
   T data;
   Node min;
   Node pre;
   Node(T data, Node pre){
     this.data = data;
     this.pre = pre;
     // 更新目前为止最小的元素（包括自己）
     if(pre!=null && pre.min.data <= data){
        this.min = pre.min;
      }else{
         this.min = this;
      }
   }
}

使用top来保存顶点

Node top;

则push、pop和min分别为

void push(T data){
  top = new Node(data=data,pre=top);
}
T pop(){
   assert top!= null;
   T result = top.data;
   top = top.pre;
   return result;
}

T min(){
   assert top!=null;
   return top.min.data;
}

 

评论

3 楼 thihy 2013-02-26  

可以把nextMinItem嵌入Node中，这样就不需要限制maxSize。

class Node{
   T data;
   Node min;
   Node pre;
   Node(T data, Node pre){
     this.data = data; 
     this.pre = pre;
     // 更新目前为止最小的元素（包括自己）
     if(pre!=null && pre.min.data <= data){
        this.min = pre.min;
      }else{
         this.min = this;
      }
   }
}

使用top来保存顶点

Node top;

则push、pop和min分别为

void push(T data){
  top = new Node(data=data,pre=top);
}
T pop(){
   assert top!= null;
   T result = top.data;
   top = top.pre;
   return result;
}

T min(){
   assert top!=null;
   return top.min.data;
}

2 楼 chenchuangfeng 2013-02-26  

hjj20040849 写道

封装的不够好，你现在只是内部测试而已，如果我外面想调用这个栈，那就有很多问题出现了……

是啊  只是基本实现三个方法而已，其他的方法和细节没写出来。

1 楼 hjj20040849 2013-02-26  

封装的不够好，你现在只是内部测试而已，如果我外面想调用这个栈，那就有很多问题出现了……