目录一、题目描述二、思路分析三、整体代码总结一、题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 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;
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);
}
运行,验证通过
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注编程网的更多内容!
--结束END--
本文标题: C语言之包含min函数的栈实例详解
本文链接: https://www.lsjlt.com/news/139673.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0