设计包含min函数的栈,时间复杂度O(1)|微软经典面试题解析

---答题基础知识储备---

栈:又名堆栈,是一种运算受限的线性表,限定仅允许在表头进行插入和删除操作。

栈

栈的基本算法:栈一般有两种基本操作,“入栈”和“出栈”。

入栈(PUSH)算法:

  1. 入栈前,首先检查栈是否已满,若栈满(TOP>n),则给出溢出信息,做出错处理;若不满,则执行步骤2;

  2. 栈指针+1,指向进栈地址(TOP = TOP+1);

  3. 将S(TOP)指向新进栈元素(S(TOP)=X),元素进栈结束;

出栈(POP)算法:

  1. 出栈前先检查栈是否已空,如果栈已空(TOP<0),则给出下溢信息,做出错处理;若非空,则执行步骤2;

  2. 将出栈的元素赋值给取它的变量(X=S(TOP));

  3. 栈指针-1,指向栈顶(TOP=TOP-1);

------

题目:

设计一个包含min函数的栈。定义栈的数据结构,要求添加一个min函数能够得到栈的最小元素;要求函数min、push以及pop的时间复杂度都是O(1)。


答题分析:

本题是要设计一个“栈”,根据栈的特性,先入栈的元素后出栈,另外,栈内要有一个min函数,用于获取当前栈内的最小元素。

哎呀,这个题的题干把我给绕住了...min函数的作用是获取当前栈中的最小元素,题干中没有说“当前”两个字,但是应该是这个意思,所以我进了一个误区。

看到题目我的第一反应,是设置一个min系统变量,在push时用来存储最小值的位置;但是,仔细一想,这样做有一个问题,全部元素push入栈之后,min变量确定的最小值,在pop时有可能被弹出,min变量标记的最小值被弹出后,如何获得当前栈中的最小值?

所以,min系统变量的方式是不行的,考虑到push入栈和pop出栈时,当前栈中的最小值都是在变化的,所以,可以用一个min辅助栈来保存变化中的最小值。

解答:

设计一个数据栈StackData和一个最小值辅助栈StackMin,

  1. PUSH操作:

    在每次向StackData中push入栈数据时,比较一下当前StackMin的栈顶元素:若StackMin栈顶元素为空,则push数据直接入两栈;若push值大于栈顶元素,则只入StackData栈;若push值小于等于StackMin栈顶元素,则push数据入两栈。

    设计包含min函数的栈

  2. POP操作
    出栈操作时,比较StackData中栈顶元素和StackMin中栈顶元素的值,如果两值相等,则共同出栈,若不相等,则只StackData栈顶元素出栈;

  3. getMin操作

    经过以上两种操作,即可知StackMin栈顶元素始终为StackData中的最小值,getMin操作即是获取StackMin的栈顶元素

代码实现:

typedef struct{
    int val;
    int min;
}stack_item;

typedef struct{
    stack_item data[STACK_LEN];
    int top;
    
}stack;

void push(stack *stk,int val){
    stk->data[++stk->top].val = val;
    if(stk->top > 0){
        if(val < stk->data[stk->top -1].min){
        // 如果push进的元素小于最小元素
            skt->data[stk->top].min = val;//将当前元素置为栈中最小元素
        }else{
        //否则,不更新最小元素
            skt->data[stk->top].min = skt->data[stk->top-1].min;
        }
    }else{
        skt->data[stk->top].min = val;
    }
}

int pop(stack *stk){
    return stk->data[skt->top--].val;
}

int min(stack *stk){
    return stk->data[skt->top].min;
}


以上用辅助栈的方法是这道题目的传统解法,另外还有一种巧妙的解法,不用辅助栈

解法思路:

push(int elem)入栈元素时,向栈中压入当前元素与最小元素的差值,然后比较当前元素与当前最小元素的大小,并将它们之间的最小值压入。

执行pop()函数,元素出栈操作时,先pop()出栈顶的两个值,这两个值分别是当前栈中最小值min和最后压入的元素与栈中最小值的差值diff。

  1. 如果diff<0,则表示最后压入栈的元素是当前栈的最小元素,弹出栈后,此时,栈中的最小元素大小为(min - diff);将(min - diff)压入栈,弹出min,完成pop()操作。

  2. 如果diff>=0且栈不为空,则表示最后压入栈的元素不是当前栈的最小元素,此时需要弹出的元素值为(min + diff);将(min + diff)弹出,将min压回栈。

  3. 如果栈为空,则表示当前元素已是栈中最后一个元素,直接弹出min即可。


代码实现:

struct minStackLessSpace{
    void push(int i){
        if(s.empty()){
            s.push(i);
            s.push(i);
        }
        if(i-s.top()<0){
            s.pop();
            s.push(i-s.top());
            s.push(i);
        }else{
            j=s.top();
            s.pop();
            s.push(i-s.top());
            s.push(j);
        }
    }
    bool pop(){
        if(s.empty()){ return false;}
        int i = s.top();
        s.pop();
        if(s.top()<0){
            int j = s.top();
            s.pop();
            s.push(i-j);
        }else{
            s.pop();
            s.push(i);
        }
    }
    int min()   
    {  
        int min = s.top();  
        return min;  
    }
}




评论

赞助商