设计一个特殊的栈，包含 min 函数。能够得到栈的最小元素。

要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

分析

由于时间复杂度的要求，我们不能用其他方法了，最简单的就是用空间换时间，给每个元素加一个min元素，表示压栈到现在最小的元素。

这样每次push时候，维护下data[top-1].min和当前val，取min值设到data[top].min即可。注意top=0时的特殊情况，min就是val。

特别提醒：企图整个栈共用一个min或者max辅助存储是错误的，因为一旦发生pop，min和max就会改变！

下面是代码，我还添加了一个max函数，也是复杂度O(1)的，原理一样，不解释了。

#include <stdio.h>

#define MAX 100

struct Node
{
	int data;
	int min;
	int max;
};

struct Stack
{
	struct Node data[MAX];
	int top;
};

void stack_init(struct Stack* stack)
{
	stack->top = 0;
}

int stack_push(struct Stack* stack, int val)
{
	if(stack->top>=MAX)
	{
		return -1;
	}
	stack->data[stack->top].data = val;
	if(stack->top==0)
	{
		stack->data[stack->top].min = stack->data[stack->top].max = val;
	}else
	{
		stack->data[stack->top].min = (val<stack->data[stack->top-1].min)?val:stack->data[stack->top-1].min;
		stack->data[stack->top].max = (val>stack->data[stack->top-1].max)?val:stack->data[stack->top-1].max;
	}
	stack->top++;
	return 0;
}

int stack_pop(struct Stack* stack, int* data)
{
	if(stack->top==0)
	{
		return -1;
	}
	*data = stack->data[--stack->top].data;
	return 0;
}

int stack_top(struct Stack* stack, int* data)
{
	if(stack->top==0)
	{
		return -1;
	}
	*data = stack->data[stack->top-1].data;
	return 0;
}

int stack_min(struct Stack* stack, int* data)
{
	if(stack->top==0)
	{
		return -1;
	}
	*data = stack->data[stack->top-1].min;
	return 0;
}

int stack_max(struct Stack* stack, int* data)
{
	if(stack->top==0)
	{
		return -1;
	}
	*data = stack->data[stack->top-1].max;
	return 0;
}
int main()
{
	struct Stack stack;
	int i;
	int tmp;
	// Init
	stack_init(&stack);
	// Push 0 ~ 50
	for(i=0;i<50;i++)
	{
		tmp = rand() % 100;
		printf("push %d\n", tmp);
		stack_push(&stack, tmp);
	}
	// Print top, min, max
	if(stack_top(&stack, &tmp)==0)
	{
		printf("top=%d\n", tmp);
	}
	if(stack_min(&stack, &tmp)==0)
	{
		printf("min=%d\n", tmp);
	}
	if(stack_max(&stack, &tmp)==0)
	{
		printf("max=%d\n", tmp);
	}
	// Pop 10
	for(i=0;i<10;i++)
	{
		stack_pop(&stack, &tmp);
	}
	// Print top, min, max
	if(stack_top(&stack, &tmp)==0)
	{
		printf("top=%d\n", tmp);
	}
	if(stack_min(&stack, &tmp)==0)
	{
		printf("min=%d\n", tmp);
	}
	if(stack_max(&stack, &tmp)==0)
	{
		printf("max=%d\n", tmp);
	}
	return 0;
}