我写故我在

I write, therefore I am

程序员面试题集002

Posted by ieipi 于 九月 14, 2011

题目
定义栈的数据结构,添加一个min函数,使之能在O(1)的时间内得到栈的最小元素.要求push,pop的时间复杂度都是O(1).
思路1
1.普通栈的push和pop操作都是O(1),但是min()操作为O(n);
2.尝试在每一次push操作时将最小值放在栈顶;但是此时不满足栈的LIFO特点;
3.继续尝试,设置一个minValue,记录当前栈的最小元素,每次push后更新该值,但是一旦该值被pop后,无法在O(1)内得到剩下元素的最小值;
4.继续尝试,可否用空间换取时间?Bingo!设置一个辅助栈,保存栈中当前元素的最小值.每次push,将最小值压栈,每次pop,也将栈顶最小元素出栈,
这样,栈顶元素既是当前元素的最小值.
源代码
/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Design a stack such that the getMinumun()operation will return the minimum
 *                  of the stack within O(1)time. And the push and pop operation will also run
 *                  in O(1)time.
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();

        stack<T> data;
        stack<T> minstack;
};
template <class T>
void MinStack<T>::push(T value)
{
    data.push(value);
    if(minstack.size() == 0){
        minstack.push(value);
    }else{
        T& min = minstack.top();
        if(value >= min){
            minstack.push(min);
        }else{
            minstack.push(value);
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    minstack.pop();
    T top = data.top();
    data.pop();
    return top;
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    return minstack.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二
是否可以不要辅助栈,从而将空间复杂度也降低到O(1)呢?
接着思路一第三步,minValue保存当前最小值,但是栈内元素可以做手脚:
当入栈元素value>=minValue时,直接压栈;
但是当value<minValue时,需要特殊处理,我们将2*value-minValue入栈,
再更新minValue到当前最小值,即value 。
pop()操作也要做相应处理:
当top>=minValue时,说明栈顶元素即是原来压栈元素,直接弹出;
但是当top<minValue时,说明栈顶元素是做过手脚之后的结果,我们需要恢复,
此时minValue值即为原压栈元素,可以直接弹出,但是需要更新minValue=2*value-top
源代码

/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Without duplicate stack.min(),push(),and pop() are O(1); space is also O(1);
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();
        T top();

        stack<T> data;
        T minValue;
};
template <class T>
void MinStack<T>::push(T value)
{
    if(data.size() == 0){
        data.push(value);
        minValue = value;
    }else{
        if(value >= minValue){
            //push the actual value into stack.
            data.push(value);
        }else{
            //update minValue which is the new incomming data.
            //construct a new value_tmp to be pushed.
            T value_tmp = (value - minValue) + value;
            data.push(value_tmp);
            minValue = value;
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    T top = data.top();
    if(top >= minValue){
        //this is the actual member.
        data.pop();
        return top;
    }else{
        //minValue is the actual pushed data.
        //use top and minValue to restore the next minValue.
        top = minValue;
        minValue = 2*top - data.top();
        data.pop();
        return top;
    }
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    return minValue;
}
template <class T>
T MinStack<T>::top()
{
    return data.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);

    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

Reference
1.http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
2.http://stackoverflow.com/questions/1377222/min-value-from-stack?answertab=active#tab-top
3.http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

 
%d 博主赞过: