面试题_设计包含 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;
                }