LeetCode: Min Stack 解题报告

Min Stack

My Submissions

Question

Solution

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.

Show Tags

Have you met this question in a real interview? Yes No

Discuss

SOLUTION 1:

比较直观。用一个min stack专门存放最小值，如果有比它小或是相等的（有多个平行的最小值都要单独存放，否则pop后会出问题），

则存放其到minstack.具体看代码：

 1 class MinStack {
 2     Stack<Integer> elements = new Stack<Integer>();
 3     Stack<Integer> minStack = new Stack<Integer>();
 4     
 5     public void push(int x) {
 6         elements.push(x);
 7         if (minStack.isEmpty() || x <= minStack.peek()) {
 8             minStack.push(x);
 9         }
10     }
11 
12     public void pop() {
13         if (elements.isEmpty()) {
14             return;
15         }
16         
17         // 这个地方太蛋疼了，居然要用equals...
18         if (elements.peek().equals(minStack.peek())) {
19             minStack.pop();
20         }
21         elements.pop();
22     }
23 
24     public int top() {
25         return elements.peek();       
26     }
27 
28     public int getMin() {
29         return minStack.peek();
30     }
31 }

View Code

2014.1229 redo.

 1 class MinStack {
 2     Stack<Integer> s = new Stack<Integer>();
 3     Stack<Integer> min = new Stack<Integer>();
 4     
 5     public void push(int x) {
 6         s.push(x);
 7         if (min.isEmpty() || x <= min.peek()) {
 8             min.push(x);
 9         }
10     }
11     
12     // Pop 1: use equals.
13     public void pop1() {
14         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="
15         if (s.peek().equals(min.peek())) {
16             min.pop();
17         }
18         s.pop();
19     }
20     
21     // Pop 2: use int
22     public void pop2() {
23         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="
24         int n1 = s.peek();
25         int n2 = min.peek();
26         if (n1 == n2) {
27             min.pop();
28         }
29         s.pop();
30     }
31     
32     // Pop 3: use (int)
33     public void pop() {
34         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="
35         if ((int)s.peek() == (int)min.peek()) {
36             min.pop();
37         }
38         s.pop();
39     }
40 
41     public int top() {
42         return s.peek();
43     }
44 
45     public int getMin() {
46         return min.peek();
47     }
48 }

View Code

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/stack/MinStack.java