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

代码：

Java代码

1. package腾讯面试题;
3. publicclassStack{
4. privateintitemCount=0;
5. privateItemminItem=null;
6. privateItem[]nextMinItem;
7. privateItemstackTop=null;
8. privateintmaxSize=100;
10. publicStack(){
11. nextMinItem=newItem[maxSize];
12. }
14. classItem{
15. intData;
16. ItemnextItem;
18. publicItem(intdata){
19. this.Data=data;
20. }
22. }
24. publicbooleanpush(Itemitem){
25. if(itemCount==maxSize){
26. System.out.println("栈已满");
27. returnfalse;
28. }
29. itemCount++;
30. if(minItem==null){
31. minItem=item;
32. }else{
33. if(item.Data<minItem.Data){
34. nextMinItem[itemCount]=minItem;
35. minItem=item;
36. }
37. }
38. item.nextItem=stackTop;
39. stackTop=item;
41. returntrue;
42. }
44. publicbooleanpop(){
45. if(itemCount==0){
46. System.out.println("栈是空的，无法出栈");
47. returnfalse;
48. }
50. if(stackTop==minItem){
51. minItem=nextMinItem[itemCount];
52. }
53. stackTop=stackTop.nextItem;
54. itemCount--;
55. returntrue;
57. }
59. publicItemmin(){
60. if(itemCount==0){
61. System.out.println("栈是空的，无最小值");
62. returnnull;
63. }
64. returnminItem;
65. }
67. /**
68. *@paramargs
69. */
70. publicstaticvoidmain(String[]args){
71. //TODOAuto-generatedmethodstub
72. Stackstack=newStack();
73. stack.push(stack.newItem(5));
74. System.out.println("push:min="+stack.min().Data+"itemCount="+stack.itemCount);
75. stack.push(stack.newItem(4));
76. System.out.println("push:min="+stack.min().Data+"itemCount="+stack.itemCount);
77. stack.push(stack.newItem(3));
78. System.out.println("push:min="+stack.min().Data+"itemCount="+stack.itemCount);
79. stack.push(stack.newItem(2));
80. System.out.println("push:min="+stack.min().Data+"itemCount="+stack.itemCount);
81. stack.push(stack.newItem(1));
82. System.out.println("push:min="+stack.min().Data+"itemCount="+stack.itemCount);
83. stack.pop();
84. System.out.println("pop:min="+stack.min().Data+"itemCount="+stack.itemCount);
85. stack.pop();
86. System.out.println("pop:min="+stack.min().Data+"itemCount="+stack.itemCount);
87. stack.pop();
88. System.out.println("pop:min="+stack.min().Data+"itemCount="+stack.itemCount);
89. stack.pop();
90. System.out.println("pop:min="+stack.min().Data+"itemCount="+stack.itemCount);
91. stack.pop();
92. System.out.println("栈结构为：\n|____1_____|\n|____2_____|\n|____3_____|\n|____4_____|\n|____5_____|\n");
95. }
96. }

运行结果：

Java代码

1. push:min=5itemCount=1
2. push:min=4itemCount=2
3. push:min=3itemCount=3
4. push:min=2itemCount=4
5. push:min=1itemCount=5
6. pop:min=2itemCount=4
7. pop:min=3itemCount=3
8. pop:min=4itemCount=2
9. pop:min=5itemCount=1
10. 栈结构为：
11. |____1_____|
12. |____2_____|
13. |____3_____|
14. |____4_____|
15. |____5_____|

博友thihy的另一种方法：

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

Java代码

1. classNode{
2. Tdata;
3. Nodemin;
4. Nodepre;
5. Node(Tdata,Nodepre){
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. }

使用top来保存顶点

Java代码

1. Nodetop;

则push、pop和min分别为

Java代码

1. voidpush(Tdata){
2. top=newNode(data=data,pre=top);
3. }
4. Tpop(){
5. asserttop!=null;
6. Tresult=top.data;
7. top=top.pre;
8. returnresult;
9. }
11. Tmin(){
12. asserttop!=null;
13. returntop.min.data;
14. }