腾讯微信面试题--实现时间复杂度为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;
}

 

评论

23 楼 martinko2009 2013-04-17  

push方法也有一个问题，你测试数据是从大到小的，如果不是那样，混编的话，如果连续两个数字都比最小值大，那第一个数据就会丢失。

22 楼 martinko2009 2013-04-17  

时间复杂度是O(1)，这点楼主没有考虑到。

21 楼 suluqiong 2013-02-28  

3楼思想代码实现

package com.my.test;

public class StackMin<T extends Comparable<T>> {
	
	/**
	 * 栈顶
	 */
	private Node<T> stackTop;
	
	/**
	 * 栈中最小值
	 */
	private Node<T> minNode;
	
	/**
	 * 栈元素数
	 */
	private int count;
	
	/**
	 * 构造函数
	 */
	public StackMin(){
		count=0;
		stackTop=null;
		minNode=null;
	}
	
	/**
	 * 入栈
	 */
	public boolean push(Node<T> node){
		
		if(node==null)
			return false;
		
		//第一次入栈
		if(count==0){
			minNode=node;
		}else{
			//设置该节点入栈前最小值节点
			node.setNextMinNode(minNode);
			
			//设置该节点下一节点
			node.setNextNode(stackTop);
			
			if(minNode.getData().compareTo(node.getData())>0){
				minNode=node;
			}
		}
		//设置栈顶
		stackTop=node;
		
		count++;
		return true;
	}
	
	/**
	 * 出栈
	 */
	public Node<T> pop(){
		
		//简单的写个返回null
		if(count==0){
			return null;
		}
		
		//保存栈顶节点
		Node<T> node=stackTop;
		
		//更新最小值节点
		minNode=stackTop.getNextMinNode();
		
		//更新栈顶
		stackTop=stackTop.getNextNode();
		
		count--;
		return node;
	}
	
	/**
	 * 最小值
	 * @return
	 */
	public Node<T> getMinNode(){
		
		return minNode;
	}
	
	public int getCount() {
		return count;
	}


	public static void main(String[] args){
		
		StackMin<Integer> stack=new StackMin<Integer>();
		stack.push(new Node<Integer>(new Integer(2)));
		stack.push(new Node<Integer>(new Integer(3)));
		stack.push(new Node<Integer>(new Integer(1)));
		stack.push(new Node<Integer>(new Integer(1)));
		
		stack.pop();
		stack.pop();
		
		System.out.println(stack.getMinNode());
	}
}


class Node<T extends Comparable<T>> {
	
	T data;
	
	/**
	 * 该元素入栈时，最小的元素
	 */
	private Node<T> nextMinNode;
	
	/**
	 * 指向前一个元素
	 */
	private Node<T> nextNode;
	
	
	public Node(T data){
		this.data=data;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node<T> getNextMinNode() {
		return nextMinNode;
	}

	public void setNextMinNode(Node<T> nextMinNode) {
		this.nextMinNode = nextMinNode;
	}

	public Node<T> getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node<T> nextNode) {
		this.nextNode = nextNode;
	}

	
	public String toString(){
		return data.toString();
	}
}

20 楼 guoguo881218 2013-02-28  

编程之美里的题

19 楼 chenchuangfeng 2013-02-28  

leonayx123 写道

只说一句。。你弹出操作时，只是返回了一个应用。。这个对象永远不会被回收。因为他会始终被你的栈的数组引用。。这是Effective java里的一个例子。

嗯对，可以把数组元素设置为null

18 楼 leonayx123 2013-02-28  

只说一句。。你弹出操作时，只是返回了一个应用。。这个对象永远不会被回收。因为他会始终被你的栈的数组引用。。这是Effective java里的一个例子。

17 楼 chenchuangfeng 2013-02-28  

410063005 写道

这题最初来自谷歌吧。 下面这个思路编码应该更简单：
设置两个栈，第一个栈对入栈元素进行正常操作，第二个栈每次入栈时栈顶元素为当前栈中最小值。 比如对 8, 3, 7, 2, 18, 19, 1这个序列， 两个栈的变化分别为：
8
8
-------
8, 3
8, 3
-------
8, 3, 7
8, 3, 3
-------
8, 3, 7, 2
8, 3, 3, 2
-------
8, 3, 7, 2, 18
8, 3, 7, 2, 2
-------
...

思路相对比较清晰    不过你这个若要真正去实现，要实现两个不同的栈结构哦...代码量会比较多，因为主栈的pop 和push 和辅助栈的是不一样的！

16 楼 410063005 2013-02-28  

这题最初来自谷歌吧。 下面这个思路编码应该更简单：
设置两个栈，第一个栈对入栈元素进行正常操作，第二个栈每次入栈时栈顶元素为当前栈中最小值。 比如对 8, 3, 7, 2, 18, 19, 1这个序列， 两个栈的变化分别为：
8
8
-------
8, 3
8, 3
-------
8, 3, 7
8, 3, 3
-------
8, 3, 7, 2
8, 3, 3, 2
-------
8, 3, 7, 2, 18
8, 3, 7, 2, 2
-------
...

15 楼 chenchuangfeng 2013-02-27  

collonn 写道

考虑到连续的push或连续的pop，那么必须要维持一个nextMinItem[n]的数组，其中n最大等于数组长度减1。同理，那么一定会遇到这样的情况：把一个新数插入到有序数组中。最快也就是lg(n)的时间时间复杂度了吧。
我觉得想达到O(1)的时间，难。。。
顺便提一下，我也遇到了此题。。。

把一个新数插入到有序数组中??你是想插到哪？nextMinItem？？

14 楼 collonn 2013-02-27  

考虑到连续的push或连续的pop，那么必须要维持一个nextMinItem[n]的数组，其中n最大等于数组长度减1。同理，那么一定会遇到这样的情况：把一个新数插入到有序数组中。最快也就是lg(n)的时间时间复杂度了吧。
我觉得想达到O(1)的时间，难。。。
顺便提一下，我也遇到了此题。。。

13 楼 di1984HIT 2013-02-27  

写的不错，还是用指针模式比较方便，也不用判断什么size了。

12 楼 chenchuangfeng 2013-02-27  

留下的祝福 写道

但是，你这个包名取得太不规范了！！

哈哈 因为我每道题用一个包...很多用英语命民都很难...所以就干脆弄个中文方面分区

11 楼 留下的祝福 2013-02-27  

但是，你这个包名取得太不规范了！！

10 楼 留下的祝福 2013-02-27  

出栈入栈，再次学习

9 楼 chenchuangfeng 2013-02-27  

lazy_ 写道

是啊   但是这道题规定不能用系统的Colletion ...

8 楼 lazy_ 2013-02-27  

底层用个LinkedList就简单多了

package algorithm.stack;

import java.util.LinkedList;

public class Stack{
	private class frame{
		private int value;
		private int minValue;
		public frame(int value, int minValue){
			this.value = value;
			this.minValue = minValue;
		}
		public int getValue() {
			return value;
		}
		public int getMinValue() {
			return minValue;
		}
	}
	
	LinkedList<frame> list = new LinkedList<frame>();
	
	Stack(){
		
	}
	
	public int min() {
		if(list.isEmpty()){
			return 0;
		}
		return list.peek().getMinValue();
	}

	public int pop() {
		if(list.isEmpty()){
			return 0;
		}
		return list.pop().getValue();
	}

	public void push(int i) {
		int min = Integer.MAX_VALUE;
		if(!list.isEmpty()){
			min = list.peek().getMinValue();
		}
		if(i<min){
			min = i;
		}
		list.push(new frame(i,min));
	}
	
	public static void main(String[] args){
		Stack stack = new Stack();
		stack.push(3);
		System.out.println(stack.min());
		stack.push(2);
		System.out.println(stack.min());
		stack.push(1);
		System.out.println(stack.min());
		stack.pop();
		System.out.println(stack.min());
	}
	
}

7 楼 jjhpeopl 2013-02-27  

thihy 写道

chenchuangfeng 写道

thihy 写道

不过 pop 和push是不是少了  size++ 和size--——

要完备的话，是需要的，以及size()方法。

写的很强大，学习了！

6 楼 thihy 2013-02-27  

chenchuangfeng 写道

thihy 写道

不过 pop 和push是不是少了  size++ 和size--——

要完备的话，是需要的，以及size()方法。

5 楼 chenchuangfeng 2013-02-26  

thihy 写道

不过 pop 和push是不是少了  size++ 和size--——

4 楼 chenchuangfeng 2013-02-26  

thihy 写道

确实是，避免了数组造成的开销，也简化了不少代码    学习了！！！