亲宝软件园·资讯

展开

C语言之包含min函数的栈

爱你哦小猪猪 人气:0

一、题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O ( 1 ) \rm{O(1)} O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();      --> 返回-3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();      --> 返回-2.

提示:各函数的调用总次数不超过 20000 次

二、思路分析

:思路分析中的一些内容和图片参考自力扣各位前辈的题解,感谢他们的无私奉献

分析

普通栈的push()pop()函数的复杂度为O(1),而获取栈最小值min()函数需要遍历整个栈,复杂度为O(N)

本题需要将min()函数复杂度降为O(1),则可通过建立辅助栈实现。栈1用于存储所有元素,入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数保持正常。栈2栈顶始终放着栈1最小元素,这样就可以实现min()函数的O(1)复杂度。

函数设计

push(x) 函数

①栈1正常进行入栈即可

②栈2则需要注意,栈2的栈顶一定是栈1的最小元素。每次入栈时,判断栈2是否为空。若为,则将x压入栈2。若栈2不为空,判断x与栈2的栈顶元素的大小关系,若x栈2的栈顶元素,则将x压入栈2。

pop()函数

①栈1正常进行出栈即可

②栈2则需要注意,栈1出栈1个元素后,栈2的栈顶元素仍然要为栈1的最小元素。每次出栈时,将出栈元素标记为y,若y等于栈2的栈顶元素,则栈2也执行出栈

top() 函数

直接返回栈1的栈顶元素即可

min() 函数

直接返回栈2的栈顶元素即可

示例

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

三、整体代码

整体代码如下

#define N 20000

//创建两个栈,栈1用于正常的入栈出栈操作,栈2用于将栈1的最小元素防在栈顶
typedef struct {
    int *Stack1;
    int *Stack2;
    int top1;
    int top2;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* MS=(MinStack*)malloc(sizeof(MinStack));
    MS->Stack1 = (int*)malloc(sizeof(int)*N);
    MS->Stack2 = (int*)malloc(sizeof(int)*N);
    MS->top1 = -1;
    MS->top2 = -1;
    return MS;
}

void minStackPush(MinStack* obj, int x) {
    obj->Stack1[++obj->top1] = x; //栈1正常入栈
    if(obj->top2 == -1){   //如果栈2是空的
        obj->Stack2[++obj->top2] = x; //将x也压入栈2
    }
    else{
        //如果栈2不空,同时x<=栈2的栈顶元素
        if(x <= obj->Stack2[obj->top2]){
            //将x压入栈2的栈顶
            obj->Stack2[++obj->top2] = x;
        }
    }

}

void minStackPop(MinStack* obj) {
    //保存栈1的栈顶元素,同时top1-1
    int a = obj->Stack1[obj->top1];
    obj->top1--;
    //如果栈1的栈顶元素等于栈2的栈顶元素,则将栈2的栈顶元素弹出,top2-1
    if(a==obj->Stack2[obj->top2]){
        obj->top2--;
    }
}

//正常返回栈1的栈顶元素即可
int minStackTop(MinStack* obj) {
    return obj->Stack1[obj->top1];
}

//正常返回栈2的栈顶元素即可
int minStackMin(MinStack* obj) {
    return obj->Stack2[obj->top2];
}

void minStackFree(MinStack* obj) {
    free(obj->Stack1);
    free(obj->Stack2);
    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 = minStackMin(obj);
 
 * minStackFree(obj);
*/

运行,验证通过

在这里插入图片描述

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!   

加载全部内容

相关教程
猜你喜欢
用户评论