Monday, July 18, 2016

155. Min Stack

Maintain two stacks. One is the normal stack and the other stores the minimum number so far. These two stacks should always have the same size. When I revisit this problem, I made a mistake in line 11.

1:  class MinStack {  
2:  private:  
3:    stack<int> stk;  
4:    stack<int> minStk;  
5:  public:  
6:    /** initialize your data structure here. */  
7:    MinStack() {  
8:    }  
9:    void push(int x) {  
10:      stk.push(x);  
11:      if (!minStk.empty()) {  
12:        minStk.push(x < minStk.top() ? x : minStk.top());  
13:      } else {  
14:        minStk.push(x);  
15:      }  
16:    }  
17:    void pop() {  
18:      if (!stk.empty()) {  
19:        stk.pop();  
20:        minStk.pop();  
21:      }  
22:    }  
23:    int top() {  
24:      if (!stk.empty()) {  
25:        return stk.top();  
26:      } else {  
27:        return -1;  
28:      }  
29:    }  
30:    int getMin() {  
31:      if (!minStk.empty()) {  
32:        return minStk.top();  
33:      } else {  
34:        return -1;  
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:   */  

No comments:

Post a Comment