2015年9月28日星期一

Lintcode: Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Have you met this question in a real interview? 
Yes
Example
Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note
min operation will never be called if there is no number in the stack


Reference my leetcode solution for the same problem:



 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
class MinStack {
private:
    vector<int> data;
    int minV;
public:
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        if(data.size() == 0) minV = number;
        else{
            int prev = minV + data.back();
            if(prev < minV) minV = prev;
        }
        data.push_back(number - minV);
    }

    int pop() {
        // write your code here
        int res = data.back() + minV;
        data.pop_back();
        if(data.back() < 0) minV = minV - data.back();
        return res;
    }

    int min() {
        // write your code here
        return ((data.back() + minV) < minV)?(data.back() + minV) : minV;
    }
};

Lintcode second:
Space: O(n)


 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
class MinStack {
public:
    vector<int> data;
    vector<int> minData;
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        // write your code here
        data.push_back(number);
        if(minData.empty() || number <= minData.back()) minData.push_back(number);
    }

    int pop() {
        // write your code here
        if(data.back() == minData.back()) minData.pop_back();
        int res = data.back();
        data.pop_back();
        return res;
    }

    int min() {
        // write your code here
        return minData.back();
    }
};










没有评论:

发表评论