Google面试题求解:对现在的Stack(栈)数据结构进行改进,加一个min()功能,使之能在常数,即O(1),时间内给出栈中的最小值。可对push()和pop()函数进行修改,但要求其时间复杂度都只能是O(1)。

已邀请:

木舟

赞同来自: 数美招聘 staticor

 
 
**分析:**要使pop,push,min都是O(1),所以肯定要牺牲点空间 

**思路1****:**在stack的数据结构中加两个个字段,如 

     typedef struct {

int data;

int top;

int min;

int second;

}stack;


          pop,push的时候都去栈顶元素,所以是O(1) 

          min的时候取stack的min字段,所以也是O(1) 

         每次push的时候进行比较,如果当前push的元素比stack->min小,则用当前元素替换stack->min,用原来的min替换second。如果当前push的元素比stack->min大,但比second小,则用当前元素替换stack->second。于是达到了取min的效果,程序如下 

         int push(stack * s,int x){

ASSERT(s!=NULL);

if(s->top>=MAX)

{

printf("Stack overload!");

return -1;

}

s->data=x;

if(xmin)

s->min=x;

return 0;

}

        每次pop的时候进行比较,如果pop的元素为min,则用second替换min。于是达到了取min的效果,程序如下 
        int pop(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty!");

return -1;

}

(*x)=s->data;
if(x==s->min) s->min=s->second;
return 0;

}

int min( stack *s,int *x )

{

ASSERT(s!=NULL);

(*x)=s->min;

return 0;

}



思路2:设置辅助栈ass,记录每个状态下的最小值,每次插入时,得到辅助栈当前值,和插入的值比较 

如果小则插入到最小值栈的就是它,否则就是原来的最小值,通过这种方式,pop,push,min三个都是 

O(1)算法的。 

 typedef struct {

int data;

int top;

}stack;

STATIC int push_stack(stack *s,int x)

{

ASSERT((s!=NULL));

if(s->top>=MAX)

{

printf("Stack overload");

return -1;

}

s->data=x;

return 0;

}

STATIC int pop_stack(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty");

return -1;

}

(*x)=s->data;

return 0;

}

int push(stack *main,stack *ass,int x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

push_stack(main,x);

if(x
{

push_stack(ass,temp);

push_stack(ass,x);

}

else

{

push_stack(ass,temp);

push_stack(ass,temp);

}

return 0;

}

int pop(stack *main,stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

pop_stack(main,x);

return 0;

}

int min(stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

pop_stack(ass,x);

push_stack(ass,(*x));

return 0;
}

要回复问题请先登录注册