程序员面试金典-面试题0302-栈的最小值

叁歲伎倆 2022-10-06 02:53 158阅读 0赞

## 程序员面试金典-面试题0302-栈的最小值 ##

这道题解的时候，刚开始出现runtime error：member access within misaligned address，具体就是因为malloc() 申请内存之后，没有对元素进行初始化，看来以后还是不能图方便。

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
    
    
    示例：
    
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/min-stack-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

typedef struct node{
        
        int val;
        struct node * next;
    }Node;
    typedef struct {
        
        Node * head;
    } MinStack;
    
    /** initialize your data structure here. */
    
    MinStack* minStackCreate() {
        
        MinStack * min_stack = malloc(sizeof(MinStack));
        Node * n = malloc(sizeof(Node));
        min_stack->head = n;
        n->val = -1;
        n->next = NULL;
        return min_stack;
    }
    
    void minStackPush(MinStack* obj, int x) {
        
        Node * h = obj->head;
        Node * temp = malloc(sizeof(Node));
        temp->val = x;
        temp->next = h->next;
        h->next = temp;
    }
    
    void minStackPop(MinStack* obj) {
        
        Node * h = obj->head;
        Node * temp = h->next;
        if(temp==NULL)
            return;
        h->next = temp->next;
        free(temp);
    }
    
    int minStackTop(MinStack* obj) {
        
        Node * h = obj->head;
        return h->next->val;
    }
    
    int minStackGetMin(MinStack* obj) {
        
        Node * h = obj->head;
        if(h->next == NULL)
            exit(-1);
        int min = h->next->val;
        Node * temp = h->next;
        while(temp!=NULL)
        {
        
            if(temp->val < min)
                min = temp->val;
            temp = temp->next;
        }
        return min;
    }
    
    void minStackFree(MinStack* obj) {
        
        Node * h = obj->head;
        Node * temp = h->next;
        while(temp!=NULL)
        {
        
            Node * t = temp->next;
            h->next = t;
            free(temp);
            temp = t;
        }
        free(h);
        free(obj);
    }
    
    /**
     * Your MinStack struct will be instantiated and called as such:
     * MinStack* obj = minStackCreate();
     * minStackPush(obj, x);
     
     * minStackPop(obj);
     
     * int param_3 = minStackTop(obj);
     
     * int param_4 = minStackGetMin(obj);
     
     * minStackFree(obj);
    */