面试题_设计包含 min函数的栈

题目

设计一个包含 min 函数的栈：在定义栈的数据结构时，额外提供一个 min 函数，用来返回当前栈内的最小元素。

要求 min、push 和 pop 三个操作的时间复杂度都必须是 O(1)。

思路

只靠一个数据栈很难在 O(1) 的时间里拿到最小值，因此引入一个与数据栈配套的"最小值栈"。每次 push 一个新元素时，同步把"截至当前为止的最小值"压入最小值栈；pop 时两个栈同步弹出；min 操作只需读取最小值栈的栈顶即可。

这样一来，三个操作都只涉及常数次的数组读写，时间复杂度均为 O(1)。

实现

下面是一份 C++ 参考实现，使用两个定长数组分别保存数据和对应的最小值。

#include <iostream>
using namespace std;

/*by hk 2015-7-1*/

#define MAX ((~(unsigned int )0)-1)/2

class stack
{
public:
	int stack_data[100];/*数据元素*/
	int stack_min[100];/*每次插入值 对于当前最小值*/
	int iter;
	int iter_min;
	stack()
	{
		iter=0;
		iter_min=1;
		stack_min[1]=MAX;
	}

	void pop()
	{
		if(iter>0)
		{
			--iter;
			--iter_min;
		}
	}

	void push(int x)
	{
		if(iter<99)
		{
			stack_data[iter++]=x;
			if(x<stack_min[iter_min-1])
			{
				stack_min[iter_min++]=x;
				stack_min[iter_min]=MAX;
			}
			else
			{
					stack_min[iter_min]=stack_min[iter_min-1];
					++iter_min;
			}
		}
	}
	int min()
	{
		return stack_min[iter_min-1];
	}
};


int main(int argc, char *argv[])
{
	stack stk;
	stk.push(7);
	stk.push(3);
	stk.push(2);
	stk.push(8);
	stk.push(1);
	stk.pop();
	cout<<stk.min();
	return 0;
}