题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是。
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
思路
在正常情况下，如果想获取栈的最小值需要遍历整个栈，复杂度为，我们可以在定义栈存储的数据结构为
Element，每个元素 Element 入栈的时候记录两个值当前值 data 与 当前栈中最小值 m，这样可以利用空间换取实际，直接获取最小值 m。
代码实现
/*为保证pop函数的时间复杂度为O(1),采用嵌套结构体，每个节点存放数据和当前最优min*/
#define MAX_SIZE 10000
//存放数据和min
typedef struct{
int data;
int min;
}Element;
//以Element结构体数组作为栈的元素
typedef struct {
Element *element;
int top;
} MinStack;
/** initialize your data structure here. */
MinStack* minStackCreate() {
MinStack *obj=(MinStack*)malloc(sizeof(MinStack));
obj->element = (Element *)malloc(sizeof(Element)*MAX_SIZE);
obj->top = -1;
return obj;
}
void minStackPush(MinStack* obj, int x) {
if(obj->top>=MAX_SIZE)
return ;
int minValue = x;
if(obj->top !=-1){
int temp = obj->element[obj->top].min;
if(temp < minValue){
minValue = temp;
}
}
int top = obj->top + 1;
obj->element[top].min = minValue;
obj->element[top].data = x;
obj->top = top;
return ;
}
void minStackPop(MinStack* obj) {
if(obj->top<0)
return ;
obj->top--;
return ;
}
int minStackTop(MinStack* obj) {
return obj->element[obj->top].data;
}
int minStackMin(MinStack* obj) {
return obj->element[obj->top].min;
}
void minStackFree(MinStack* obj) {
free(obj);
}
