题目
题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
除了有push和pop操作外，还有一个min函数返回栈中的最小值， push，pop和min函数的时间复杂度都要为O(1)。
思路
push和pop操作很明显就是O（1）的时间复杂度，关键是min函数，一般来说，我们求栈中的最小值，会从栈顶开始遍历栈，并设置一个变量Min来保存每次遍历时的最小值 ，遍历到比Min还小的元素，就将该元素赋给Min，但这种方法的时间复杂度为O（n）。
我们可以考虑用空间换时间的思想来提高时间复杂度（很多时候时空均衡都是提高时间复杂度的常规思路），我们另外可以设置一个同样最大深度的栈来保存对应序列的最小值。比如，我们以数组来模拟栈，假设栈A的最大深度为100，目前深度为10，我们就可以另外建立一个栈B，也设它的最大深度为100，另外，让B的前10个元素保存对应位置到栈底位置间元素的最小值，比如,B[3]保存A[3]、A[2]、A[1]、A[0]这几个元素中的最小值，B[2]保存A[2]、A[1]、A[0]这几个元素中的最小值….B[0]则直接保存A[0]的值。这样，我们求栈的最小元素时，直接返回B数组中对应位置的元素值即可。
/*
输入：
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=1000000)， n代表将要输入的操作的步骤数。
接下来有n行，每行开始有一个字母Ci。
Ci=’s’时，接下有一个数字k，代表将k压入栈。
Ci=’o’时，弹出栈顶元素。
输出：
对应每个测试案例中的每个操作，
若栈不为空，输出相应的栈中最小元素。否则，输出NULL。
样例输入：
7
s 3
s 4
s 2
s 1
o
o
s 0
样例输出：
3
3
2
1
2
3
0
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000 //栈的容量 如果栈的深度我们设为 1000000，运行出错，报stack overflow异常
typedef int ElementType;
//全局变量，指向栈顶 ，即栈顶指针
int top=-1;
bool push(ElementType *arr,ElementType val){
if(arr==NULL||top>MAX-1){
return false;
}
arr[++top]=val;
return true;
}
bool pop(){
if(top<=-1){
return false;
}
--top;
return true;
}
void updateMinArr(ElementType *my_stack,ElementType * MinArr){
if(top>MAX-1||top==-1){
return;
}
else{
MinArr[0]=my_stack[0];
int index=1;
while(index<=top){
if(my_stack[index]<MinArr[index-1])
MinArr[index]=my_stack[index];
else{
MinArr[index]=MinArr[index-1];
}
index++;
}
}
}
ElementType my_min(ElementType *MinArr){
return MinArr[top];
}
int main(void){
int n;
ElementType my_stack[MAX]; //用此数组来模拟栈
ElementType MinArr[MAX];//用此数组来保存最小值，即第i个位置保存的是my_stack数组中前i个元素中的最小值
//printf("wuwu");
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
while(getchar()!='\n')//跳过缓冲流中的换行字符
continue;
char ch;
scanf("%c",&ch);
if(ch=='s'){//进栈
ElementType val;
scanf("%d",&val);
push(my_stack,val);
}
else if(ch=='o'){//出栈
pop();
}
updateMinArr(my_stack,MinArr);//经过一个入栈和出栈后，更新数组Min ,在这里有一点不太好，每当我们push或pop后，都要全部更新Min数组，花费时间太长
if(top>-1&&top<MAX){
printf("%d\n",my_min(MinArr));
}
else{
printf("NULL\n");
}
}
}
return 0;
}