155. Min Stack

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/min-stack/description/

想法

比较简单，就用一个栈来记录原栈底到当前顶的最小值，每次push的时候决定是否放进栈里。

答案

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

感想

自己想得有些多了。
其实本来只在push的时候判断下就可以了，因为如果没把第二小的push进去，第二小也会在最小之前pop，不会发生最小无法维护的情况。