《剑指Offer》面试题:实现O(1)获取min的栈

时间:2021-11-03 22:52:18

题目

题目描述:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的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;
}