题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
C++:利用map实现整体时间复杂度O(1)
vector实际上就是一个stack的封装类。所以直接用vector的成员函数就可以很容易的实现栈的基础操作。
public: vector<int> pool; void push(int value) { //不能这么写:pool[head] = value; 在最开始,vector没有申请到任何空间,因此pool[head]这个访问操作 //是非法的。访问操作不会申请额外空间。 pool.push_back(value); } void pop() { pool.pop_back(); } int top() { return pool.back(); }
重点在这:
请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
最容易想到的方法当然是从头到尾查询整个栈中最小值,但这个方法是O(N)的,显然不可行。
当然你也可以把这个时间成本转移到其他函数:
维护一个int类的mini变量,在每一次对栈有修改,即入栈push或出栈pop操作完成后,从头到尾查询栈中的最小值,用该值更新mini。调用min()函数时直接返回mini的值即可。
题目是过了,但其实也只是在骗自己XD,面试官当然不会对这个答案感到满意。
我给出的解决方案是:使用键值对数组map以空间换时间。
维护一个键和值都为int类型的map容器times,在每次对栈进行修改时,我们在times中进行相应的“记录”。
public: vector<int> pool; map<int,int> times;//<栈中元素的值,出现次数> void push(int value) { pool.push_back(value); times[value]++;//使times中键为value的值++ } void pop() { //将即将出栈的元素作为键,使其对应的值--,并检查该值是否还在栈中存在(出现次数是否为0) if(--times[pool.back()] == 0) { times.erase(pool.back());//已不在栈中存在的值,我们将其对应的键值对从times中移除掉 } pool.pop_back(); } int top() { return pool.back(); }
对于键值对map容器来说,通过下标访问/修改一个键的值,就像我们所熟知的int类数组通过下标访问一个元素一样,时间复杂度是都是O(1),所以更新栈操作push、pop的时间复杂度也为O(1)。
注意当一个数不再存在在栈中时,我们要将其从times中移除掉,而不是只将他的值改为0。否则最后这招就不好使了:
int min() { return times.begin()->first; }
map容器中的各个元素是按 键key 进行排序的。对于int类型的键自然是按大小排序了,所以times中的第一个元素times.begin()的键就是我们要找的最小值。用->first访问一个键值对的键,用->second来得到它的值。
这样,整个类中的各个函数我们都实现了时间复杂度为O(1)。