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

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 stubStack 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=1push:min=4 itemCount=2push:min=3 itemCount=3push:min=2 itemCount=4push:min=1 itemCount=5pop :min=2 itemCount=4pop :min=3 itemCount=3pop :min=4 itemCount=2pop :min=5 itemCount=1栈结构为：|____1_____||____2_____||____3_____||____4_____||____5_____|

Java代码??

1. class?Node{??
2. ???T?data;??
3. ???Node?min;??
4. ???Node?pre;??
5. ???Node(T?data,?Node?pre){??
6. ?????this.data?=?data;???
7. ?????this.pre?=?pre;??
8. ?????//?更新目前为止最小的元素（包括自己）??
9. ?????if(pre!=null?&&?pre.min.data?<=?data){??
10. ????????this.min?=?pre.min;??
11. ??????}else{??
12. ?????????this.min?=?this;??
13. ??????}??
14. ???}??
15. }??

Java代码??

1. Node?top;??

Java代码??

1. void?push(T?data){??
2. ??top?=?new?Node(data=data,pre=top);??
3. }??
4. T?pop(){??
5. ???assert?top!=?null;??
6. ???T?result?=?top.data;??
7. ???top?=?top.pre;??
8. ???return?result;??
9. }??
10. ??
11. T?min(){??
12. ???assert?top!=null;??
13. ???return?top.min.data;??
14. }??

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;}

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());}} 9 楼 chenchuangfeng 22 小时前 lazy_ 写道
是啊 但是这道题规定不能用系统的Colletion ...
10 楼 留下的祝福 21 小时前 出栈入栈，再次学习 11 楼 留下的祝福 20 小时前 但是，你这个包名取得太不规范了！！ 12 楼 chenchuangfeng 20 小时前 留下的祝福 写道但是，你这个包名取得太不规范了！！
哈哈 因为我每道题用一个包...很多用英语命民都很难...所以就干脆弄个中文方面分区 13 楼 di1984HIT 19 小时前 写的不错，还是用指针模式比较方便，也不用判断什么size了。 14 楼 collonn 14 小时前 考虑到连续的push或连续的pop，那么必须要维持一个nextMinItem[n]的数组，其中n最大等于数组长度减1。同理，那么一定会遇到这样的情况：把一个新数插入到有序数组中。最快也就是lg(n)的时间时间复杂度了吧。
我觉得想达到O(1)的时间，难。。。
顺便提一下，我也遇到了此题。。。 15 楼 chenchuangfeng 14 小时前 collonn 写道考虑到连续的push或连续的pop，那么必须要维持一个nextMinItem[n]的数组，其中n最大等于数组长度减1。同理，那么一定会遇到这样的情况：把一个新数插入到有序数组中。最快也就是lg(n)的时间时间复杂度了吧。
我觉得想达到O(1)的时间，难。。。
顺便提一下，我也遇到了此题。。。
把一个新数插入到有序数组中??你是想插到哪？nextMinItem？？ 16 楼 410063005 3 小时前 这题最初来自谷歌吧。 下面这个思路编码应该更简单：
设置两个栈，第一个栈对入栈元素进行正常操作，第二个栈每次入栈时栈顶元素为当前栈中最小值。 比如对 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
-------
... 17 楼 chenchuangfeng 2 小时前 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 和辅助栈的是不一样的！ 18 楼 leonayx123 7 分钟前 只说一句。。你弹出操作时，只是返回了一个应用。。这个对象永远不会被回收。因为他会始终被你的栈的数组引用。。这是Effective java里的一个例子。