Google面试题（六）

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

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

思路：1：在stack的数据结构中加两个个字段，如

     typedef struct {

           int data[MAX];

           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[s->top++]=x;

                 if(x<s->min)

                  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[s->top--];
            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[MAX];

     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[s->top++]=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[s->top--];

       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<temp)

       {

               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;
}

评论

11 楼 loveofgod 2008-02-18  

在push时将每个数包装成一个结点，如果这样的话，当push的点很大时，空间复杂度会很高

10 楼 loveofgod 2008-02-18  

ddbird，那你说pop push min的复杂度多少，嗯对，push没问题，pop的时候会出问题

9 楼 JohnnyJian 2008-02-16  

引用

我认为min() O(1)的做法应该是在push时将每个数包装成一个结点，结点中两个数，一个是要压入的数，另一个记录压入前已经在栈中的的最小值。后面的就容易了，我不说了。

You're right!

8 楼 ggggqqqqihc 2008-02-15  

我认为min() O(1)的做法应该是在push时将每个数包装成一个结点，结点中两个数，一个是要压入的数，另一个记录压入前已经在栈中的的最小值。后面的就容易了，我不说了。

7 楼 zuroc 2008-02-15  

这个好像很简单?
还是我的理解有问题.........

6 楼 JohnnyJian 2008-02-15  

引用

min是O(1) 用堆就可以了，但是要pop push min 都 O(1) 似乎有难度。

RE，我就是这个意思……

5 楼 ddbird 2008-02-15  

min是O(1) 用堆就可以了，但是要pop push min 都 O(1) 似乎有难度。

4 楼 ddbird 2008-02-15  

引用

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

连续push 5个数 然后连续pop 3次，second 是什么值？？？
光用一个second就能起到排序的作用？？？ 明显不对的！

3 楼 loveofgod 2008-02-15  

请问哪里错了？上面的解答难道不是O(1)吗？

2 楼 JohnnyJian 2008-02-14  

而且我怀疑求min是否有O(1)的算法，因为即使用优先队列，也要O(logN)的复杂度……

1 楼 JohnnyJian 2008-02-14  

这是官方的答案吗？好像都是错的哦……