面试经典-设计包含min函数的栈

工程师邦威技术 2022年11月8日

0 收藏 779 点赞 1,435 浏览 1453 个字

问题：设计包含min函数的栈（栈）定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。

解答:push 和pop的时间复杂度都是O（1），这个很好理解，创建个栈即可。但是min的复杂度也是O(1)，每次push，pop后，调用min的复杂度也得是O(1)。这就要求栈中的每个元素都要存一个每个元素到栈底元素的最小值，这样来实现min的时间复杂度O(1)，只需返回栈顶元素存的最小值即可。

栈的实现代码如下：

struct MinStackElement
{
int data;
int min;
};struct MinStack
{
MinStackElement *data;
int stackSize;
int top;
};
//初始化一个栈
void MinStackInit(int maxSize,MinStack &stack)
{
stack.data=new MinStackElement[maxSize];
stack.top=0;
stack.stackSize=maxSize;
}
//释放栈的空间
void freeStack(MinStack &stack)
{
delete []stack.data;
stack.data=NULL;
stack.top=0;
stack.stackSize=0;
}//压栈
void push(int value,MinStack &stack)
{
if(stack.top==stack.stackSize)
return;stack.data[stack.top].data=value;if(stack.top==0)stack.data[stack.top].min=value;//第一个元素当然就是最小值
else
stack.data[stack.top].min=value>stack.data[stack.top-1].min?stack.data[stack.top-1].min:value;//不是第个一元素最小值需要比较一下stack.top++;
}int pop(MinStack &stack)
{if(stack.top==0)
return -1;int t= stack.data[stack.top].data;stack.top--;return t;
}int min(MinStack stack)
{
if(stack.top==0)
return -1;return stack.data[stack.top-1].min;
}

测试代码如下：

int _tmain(int argc, _TCHAR* argv[])
{
MinStack st1;MinStackInit(5,st1);push(5,st1);push(10,st1);push(1,st1);push(6,st1);push(0,st1);std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
std::cout<<min(st1);
pop(st1);
freeStack(st1);int j;std::cin>>j;return 0;
}