leetcode-min-stack

发表于   |   分类于 ，   |  

题目大意

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

　　让你实现一个栈，操作有压入，弹出，获取栈顶，以及获取最小值，要求每种时间复杂度为O(1)

题目分析

　　本题参考了disscuss区的巧妙解法，竟然用了一个数组（栈）就实现了，巧妙之处在与压栈和出栈，每次压栈时都要检测min是否会被更新，如果会被更新，则先要把旧的min压入栈，然后再压入元素的值。出栈时要检测min和栈顶是否相同，如果相同说明min的值需要用旧的值替代。还要注意，压栈判断条件if (x <= min)必须有等号，如果没有等号，意味着等于min的元素进栈时只压栈了一次，而出栈判断min == top时要出栈两次,这就造成了不正确

代码

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
39
40
41
42
43
class MinStack {
public:
    /** initialize your data structure here. */
    vector<int> data;
    int min;
    MinStack() {
        min = 0x7fffffff;
    }
    
    void push(int x) {
        if (x <= min) { //注意一定要有等号
            data.push_back(min);
            min = x;
        }
        data.push_back(x);
    }
    
    void pop() {
        int v = data.back();
        data.pop_back();
        if (v == min) {
            min = data.back();
            data.pop_back();
        }
    }
    
    int top() {
        return data.back();
    }
    
    int getMin() {
        return min;
    }
};
/**
 * 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();
 */