V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
fszaer
V2EX  ›  问与答

求 leetcode Min Stack 的 C 语言解

  •  
  •   fszaer · 2015-05-05 23:15:11 +08:00 · 3560 次点击
    这是一个创建于 3489 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原题链接
    https://leetcode.com/problems/min-stack/
    题意简单而言就是要实现一个快速求min的stack
    这题本身不难,其实我用js已经AC了
    但是当我用C重写一遍后一直re,我翻了leetcode的论坛没有发现我这个错误相关的问题在哪,也没有发现一个可行的C语言版题解,所以来这里问问
    这里是我的reC语言解

    typedef struct {
        int *number;
        int *min;
        int ntop;
        int mtop;
    } MinStack;
    
    void minStackCreate(MinStack *stack, int maxSize) {
        stack->number = (int*)malloc(maxSize*sizeof(int));
        stack->min = (int*)malloc(maxSize*sizeof(int));
        stack->mtop = stack->ntop = 0;
        stack->maxSize = maxSize;
    }
    
    void minStackPush(MinStack *stack, int element) {
        stack->number[stack->ntop++] = element;
        if (stack->mtop != 0) {
            if (element <= stack->min[stack->mtop - 1])
                stack->min[stack->mtop++] = element;
        }
        else
            stack->min[stack->mtop++] = element;
    }
    
    void minStackPop(MinStack *stack) {
        int temp = stack->number[stack->ntop--];
        if (temp == stack->min[stack->mtop - 1])
            stack->mtop--;
    }
    
    int minStackTop(MinStack *stack) {
        return stack->number[stack->ntop - 1];
    }
    
    int minStackGetMin(MinStack *stack) {
        return stack->min[stack->mtop - 1];
    }
    
    void minStackDestroy(MinStack *stack) {
        free(stack->min);
        free(stack->number);
    }
    
    6 条回复    2015-06-11 14:56:44 +08:00
    jiang42
        1
    jiang42  
       2015-05-06 03:28:04 +08:00
    把两个free去掉。。。
    Andiry
        2
    Andiry  
       2015-05-06 06:51:57 +08:00   ❤️ 1
    因为槽点实在太多,所以自己写了一个

    typedef struct {
    int *number;
    int *min;
    int top;
    int maxSize;
    } MinStack;

    void minStackCreate(MinStack *stack, int maxSize) {
    stack->number = (int*)malloc(maxSize*sizeof(int));
    stack->min = (int*)malloc(maxSize*sizeof(int));
    stack->top = 0;
    stack->maxSize = maxSize;
    }

    void minStackPush(MinStack *stack, int element) {
    int top = stack->top;

    if (top >= stack->maxSize - 1)
    return;

    stack->number[top] = element;
    if (top == 0) {
    stack->min[top] = element;
    } else {
    int min = stack->min[top - 1];
    if (element < min)
    stack->min[top] = element;
    else
    stack->min[top] = min;
    }

    stack->top++;
    }

    void minStackPop(MinStack *stack) {
    if (stack->top == 0)
    return;
    stack->top--;
    }

    int minStackTop(MinStack *stack) {
    if (stack->top == 0)
    return 0;
    return stack->number[stack->top - 1];
    }

    int minStackGetMin(MinStack *stack) {
    if (stack->top == 0)
    return 0;
    return stack->min[stack->top - 1];
    }

    void minStackDestroy(MinStack *stack) {
    free(stack->min);
    free(stack->number);
    }
    Andiry
        3
    Andiry  
       2015-05-06 06:52:48 +08:00
    缩进全都没有了,随便看看吧
    jky
        4
    jky  
       2015-05-06 08:04:39 +08:00
    void minStackPush(MinStack *stack, int element) {
    if (stack->ntop == stack->maxSize) return;
    ...
    }
    fszaer
        5
    fszaer  
    OP
       2015-05-06 09:11:31 +08:00
    @Andiry
    啊,谢谢指教,参考了你的代码
    终于知道哪里出了问题,才发现自己对边际条件的检查还不够
    billwsy
        6
    billwsy  
       2015-06-11 14:56:44 +08:00
    push和pop检查有没有超出maxSize或0, 另外pop中int temp = stack->number[--stack->ntop];
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2845 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 08:44 · PVG 16:44 · LAX 00:44 · JFK 03:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.