求 leetcode Min Stack 的 C 语言解

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3501 天前的主题，其中的信息可能已经有所发展或是发生改变。

原题链接
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);
}

Stack

mtop

minstack

6 条回复 • 2015-06-11 14:56:44 +08:00

jiang42

2015-05-06 03:28:04 +08:00

把两个free去掉。。。

Andiry

2015-05-06 06:51:57 +08:00

因为槽点实在太多，所以自己写了一个

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

2015-05-06 06:52:48 +08:00

缩进全都没有了，随便看看吧

jky

2015-05-06 08:04:39 +08:00

void minStackPush(MinStack *stack, int element) {
if (stack->ntop == stack->maxSize) return;
...
}

fszaer

2015-05-06 09:11:31 +08:00

@Andiry
啊，谢谢指教，参考了你的代码
终于知道哪里出了问题，才发现自己对边际条件的检查还不够

billwsy

2015-06-11 14:56:44 +08:00

push和pop检查有没有超出maxSize或0，另外pop中int temp = stack->number[--stack->ntop];