[CareerCup]Stacks and Queues—Q3.1

題目：

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

翻譯：

要求實現一個棧，除了有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數組中對應位置的元素值即可。

實現代碼：

/****************************************************
題目描述：
實現一個棧的push、pop操作和min操作（返回棧中最小值），
要求push，pop和min函數的時間復雜度都為O(1)
Date:2014-03-26
*****************************************************/

/*
本程序采用數組模擬棧
*/
typedef int ElemType;
#define MAX 100  //棧的深度
#include

/*
在棧頂索引指針為top時，向棧A中壓入數據data
*/
bool push(int *A,int &top,ElemType data)
{
	if(top>=MAX-1 || top<-1)
		return false;

	A[++top] = data;
	return true;
}

/*
在棧頂索引指針為top時，出棧
*/
bool pop(int &top)
{
	if(top<0)
		return false;

	top--;
	return true;
}

/*
棧頂當前索引指針為top，Min數組最大深度也為MAX，
且Min的有效元素數與棧A中的元素個數相同，
它的對應位置用來保存棧A對應位置到棧底這一部分元素中的最小值
*/
void minAll(int *A,int *Min,int top)
{
	if(top>MAX-1)
		return ;
	Min[0] = A[0];
	int i;
	for(i=1;i<=top;i++)
	{
		if(Min[i-1] > A[i])
			Min[i] = A[i];
		else
			Min[i] = Min[i-1];
	}
}

/*
返回棧頂為top時棧中元素的最小值
*/
int min(int *Min,int top)
{
	return Min[top];
}

int main()
{
	int A[MAX];
	int top = -1;
	push(A,top,4);
	push(A,top,7);
	push(A,top,2);
	push(A,top,6);
	push(A,top,3);
	push(A,top,8);
	push(A,top,5);
	push(A,top,1);

	int Min[MAX];
	minAll(A,Min,7);
	int i;
	for(i=0;i<=top;i++)
		printf(%d ,Min[i]);
	printf(
);
	/*
	int min7 = min(Min,7);
	printf(%d
,min7);
	pop(top);
	int min6 = min(Min,6);
	printf(%d
,min6);
	*/
	return 0;
}

注：代碼開源到我的Github：https://github.com/mmc-maodun/CareerCup