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

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

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

入栈（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数据入两栈。

   

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