Cracking the coding interview--Q3.2

December 19, 2012
作者:Hawstein
出处:http://hawstein.com/posts/3.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。



题目

原文:

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掉的栈顶元素就是最小值,那么我们如何更新最小值呢?显然不太好办。 既然只用一个变量没法解决这个问题,那我们就增加变量。如果说每个结点除了保存当前的 值,另外再保存一个从该结点到栈底的结点中的最小值。那么,不论哪个结点成为了栈顶结 点,我们都有办法取得剩下的这些元素的最小值。代价是付出的空间多了一倍。

代码如下:

const int MAX_INT = ~(1<<31);//2147483647

typedef struct node{
	int val, min;
}node;

class StackWithMin{
public:
	StackWithMin(int size=1000){
		buf = new node[size];
		buf[0].min = MAX_INT;
		cur = 0;
	}
	~StackWithMin(){
		delete[] buf;
	}
	void push(int val){
		buf[++cur].val = val;
		if(val<buf[cur-1].min) buf[cur].min = val;
		else buf[cur].min = buf[cur-1].min;
	}
	void pop(){
		--cur;
	}
	int top(){
		return buf[cur].val;
	}
	bool empty(){
		return cur==0;
	}
	int min(){
		return buf[cur].min;
	}

private:
	node *buf;
	int cur;
};

这种实现方式有一个明显的问题:数据冗余。比如说,栈里的数据从栈底到栈顶是1到10000, 那么,每个结点保存的最小值都是1,也就是保存了1的10000份拷贝,有这个必要吗? 直觉告诉我们应该是没必要的,我们应该可以想办法只保留一份1的拷贝, 然后如果结点是这些1到10000,就正确地返回这个最小值。这个要怎么做呢? 我们假设除了用一个栈s1来保存数据,还用另一个栈s2来保存这些非冗余最小值。那么, 当我们将数据压到要s1时,同时将它和s2的栈顶元素比较,如果不大于s2的栈顶元素, 那么将当前值也压入s2中。这样一来,s2中保存的就是一个阶段性最小值。 即s2中的每个值都是s1中栈底到达某个位置的最小值。那么,如果执行pop操作呢? 执行pop操作除了将s1中的栈顶元素出栈,还要将它和s2中的栈顶元素比较,如果相等, 说明这个值是栈底到栈顶的最小值,而它出栈后,最小值就不再是它了。所以, s2也要将栈顶元素出栈,新的栈顶元素将对应s1剩下元素中新的最小值。

代码如下:

class stack{
public:
	stack(int size=1000){
		buf = new int[size];
		cur = -1;
	}
	~stack(){
		delete[] buf;
	}
	void push(int val){
		buf[++cur] = val;
	}
	void pop(){
		--cur;
	}
	int top(){
		return buf[cur];
	}
	bool empty(){
		return cur==-1;
	}

private:
	int *buf;
	int cur;
};

class StackWithMin1{
public:
	StackWithMin1(){

	}
	~StackWithMin1(){

	}
	void push(int val){
		s1.push(val);
		if(val<=min())
			s2.push(val);
	}
	void pop(){
		if(s1.top()==min())
			s2.pop();
		s1.pop();
	}
	int top(){
		return s1.top();
	}
	bool empty(){
		return s1.empty();
	}
	int min(){
		if(s2.empty()) return MAX_INT;
		else return s2.top();
	}

private:
	stack s1, s2;
};

完整代码如下:

#include <iostream>
using namespace std;

const int MAX_INT = ~(1<<31);//2147483647

typedef struct node{
	int val, min;
}node;

class StackWithMin{
public:
	StackWithMin(int size=1000){
		buf = new node[size];
		buf[0].min = MAX_INT;
		cur = 0;
	}
	~StackWithMin(){
		delete[] buf;
	}
	void push(int val){
		buf[++cur].val = val;
		if(val<buf[cur-1].min) buf[cur].min = val;
		else buf[cur].min = buf[cur-1].min;
	}
	void pop(){
		--cur;
	}
	int top(){
		return buf[cur].val;
	}
	bool empty(){
		return cur==0;
	}
	int min(){
		return buf[cur].min;
	}

private:
	node *buf;
	int cur;
};

class stack{
public:
	stack(int size=1000){
		buf = new int[size];
		cur = -1;
	}
	~stack(){
		delete[] buf;
	}
	void push(int val){
		buf[++cur] = val;
	}
	void pop(){
		--cur;
	}
	int top(){
		return buf[cur];
	}
	bool empty(){
		return cur==-1;
	}

private:
	int *buf;
	int cur;
};

class StackWithMin1{
public:
	StackWithMin1(){

	}
	~StackWithMin1(){

	}
	void push(int val){
		s1.push(val);
		if(val<=min())
			s2.push(val);
	}
	void pop(){
		if(s1.top()==min())
			s2.pop();
		s1.pop();
	}
	int top(){
		return s1.top();
	}
	bool empty(){
		return s1.empty();
	}
	int min(){
		if(s2.empty()) return MAX_INT;
		else return s2.top();
	}

private:
	stack s1, s2;
};
int main(){
	//cout<<MIN_INT<<endl;
	StackWithMin1 mystack;//StackWithMin mystack;
	for(int i=0; i<20; ++i)
		mystack.push(i);
	cout<<mystack.min()<<" "<<mystack.top()<<endl;
	mystack.push(-100);
	mystack.push(-100);
	cout<<mystack.min()<<" "<<mystack.top()<<endl;
	mystack.pop();
	cout<<mystack.min()<<" "<<mystack.top()<<endl;
	return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview