[LeetCode] 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

例子，

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

这个题我给出两种解法，一种用了两个stack，一种只需要用一个stack。两种做法的复杂度都是

时间O(1)

空间O(n)

1. 两个stack。创建两个stack，一个叫stack，另一个叫做minstack。

push() - 每当需要push的时候，元素会被正常push到stack，同时需要看一下当前元素与min的关系，以决定是否需要把这个元素push到minStack。minStack只push当前遍历到的最小值。

pop() - stack会正常pop出当前元素；因为minStack的顶端存的永远是当前的最小值，所以当stack弹出一个元素的时候，需要去minStack看一下这个元素是不是最小值，如是，也需要从minStack弹出，这样minStack顶端保留的永远是最小值。

top() - 同peek，只是看一下stack顶端的元素

getMin() - 去peek minStack顶端的元素，因为minStack的顶端永远是当前遍历到的最小值

JavaScript实现

 1 /**
 2  * initialize your data structure here.
 3  */
 4 var MinStack = function () {
 5     this.stack = [];
 6     this.minStack = [];
 7 };
 8 
 9 /** 
10  * @param {number} x
11  * @return {void}
12  */
13 MinStack.prototype.push = function (x) {
14     this.stack.push(x);
15     if (this.minStack.length) {
16         let top = this.minStack[this.minStack.length - 1];
17         if (x <= top) {
18             this.minStack.push(x);
19         }
20     } else {
21         this.minStack.push(x);
22     }
23 };
24 
25 /**
26  * @return {void}
27  */
28 MinStack.prototype.pop = function () {
29     let pop = this.stack.pop();
30     let top = this.minStack[this.minStack.length - 1];
31     if (pop === top) {
32         this.minStack.pop();
33     }
34 };
35 
36 /**
37  * @return {number}
38  */
39 MinStack.prototype.top = function () {
40     return this.stack[this.stack.length - 1];
41 };
42 
43 /**
44  * @return {number}
45  */
46 MinStack.prototype.getMin = function () {
47     return this.minStack[this.minStack.length - 1];
48 };
49 
50 /**
51  * Your MinStack object will be instantiated and called as such:
52  * var obj = new MinStack()
53  * obj.push(x)
54  * obj.pop()
55  * var param_3 = obj.top()
56  * var param_4 = obj.getMin()
57  */

Java实现

 1 class MinStack {
 2     private Stack<Integer> stack;
 3     private Stack<Integer> minStack;
 4     /** initialize your data structure here. */
 5     public MinStack() {
 6         stack = new Stack<>();
 7         minStack = new Stack<>();
 8     }
 9     
10     public void push(int x) {
11         stack.push(x);
12         if (!minStack.isEmpty()) {
13             int min = minStack.peek();
14             if (x <= min) {
15                 minStack.push(x);
16             }
17         } else {
18             minStack.push(x);
19         }
20     }
21     
22     public void pop() {
23         int x = stack.pop();
24         if (x == minStack.peek()) {
25             minStack.pop();
26         }
27     }
28     
29     public int top() {
30         return stack.peek();
31     }
32     
33     public int getMin() {
34         return minStack.peek();
35     }
36 }
37 
38 /**
39  * Your MinStack object will be instantiated and called as such:
40  * MinStack obj = new MinStack();
41  * obj.push(x);
42  * obj.pop();
43  * int param_3 = obj.top();
44  * int param_4 = obj.getMin();
45  */

2. 一个stack，同时创建一个变量记录最小值min。

push() - push的时候看一下当前元素是否比min小，若是则把上一个min放进stack，同时更新当前最小值min。

pop() - 如果弹出值 == 当前最小值，那么再弹一次的值为上一个最小值也即出栈后更新的最小值

top() - 同peek，只是看一下stack顶端的元素

getMin() - 输出min即可

JavaScript实现

 1 /**
 2  * initialize your data structure here.
 3  */
 4 var MinStack = function () {
 5     this.stack = [];
 6     this.min = Number.MAX_SAFE_INTEGER;
 7 };
 8 
 9 /** 
10  * @param {number} x
11  * @return {void}
12  */
13 MinStack.prototype.push = function (x) {
14     // 当前值比min值更小
15     if (this.min >= x) {
16         // 将上一个min最小值保存入栈
17         this.stack.push(this.min);
18         // 更新当前最小值
19         this.min = x;
20     }
21     this.stack.push(x)
22 };
23 
24 /**
25  * @return {void}
26  */
27 MinStack.prototype.pop = function () {
28     // 如果弹出值 == 当前最小值，那么再弹一次的值为上一个最小值也即出栈后更新的最小值
29     if (this.stack.pop() == this.min) {
30         this.min = this.stack.pop();
31     }
32 };
33 
34 /**
35  * @return {number}
36  */
37 MinStack.prototype.top = function () {
38     return this.stack[this.stack.length - 1];
39 };
40 
41 /**
42  * @return {number}
43  */
44 MinStack.prototype.getMin = function () {
45     return this.min;
46 };
47 
48 /**
49  * Your MinStack object will be instantiated and called as such:
50  * var obj = new MinStack()
51  * obj.push(x)
52  * obj.pop()
53  * var param_3 = obj.top()
54  * var param_4 = obj.getMin()
55  */

Java实现

 1 class MinStack {
 2     int min = Integer.MAX_VALUE;
 3     Stack<Integer> stack = new Stack<>();
 4 
 5     /** initialize your data structure here. */
 6     public MinStack() {
 7 
 8     }
 9 
10     public void push(int x) {
11         if (x <= min) {
12             stack.push(min);
13             min = x;
14         }
15         stack.push(x);
16     }
17 
18     public void pop() {
19         if (stack.pop() == min) {
20             min = stack.pop();
21         }
22     }
23 
24     public int top() {
25         return stack.peek();
26     }
27 
28     public int getMin() {
29         return min;
30     }
31 }
32 
33 /**
34  * Your MinStack object will be instantiated and called as such:
35  * MinStack obj = new MinStack();
36  * obj.push(x);
37  * obj.pop();
38  * int param_3 = obj.top();
39  * int param_4 = obj.getMin();
40  */

LeetCode 题目总结