实现一个栈，要求Push/Pop/Min(返回最小值)的时间复杂度为O(1)

水深无声 2022-09-23 03:58 123阅读 0赞

题目：实现一个栈，要求Push/Pop/Min(返回最小值)的时间复杂度为O(1)

<span style="font-family:Microsoft YaHei;font-size:24px;">#pragma once 
    
    #include<stack>
    
    //实现一个栈，要求实现Push/Pop/Min(返回最小值)的时间复杂度为O(1)
    //栈的入栈和出栈操作本来就是时间复杂度为O（1），但是要求返回Min(最小值)
    //也是O（1）的算法，这就有些难度了，题目中 只要求了时间复杂度为O(1）,但是
    //没有要求空间复杂度，所以，我们可以以这种思想进行解决这道题，所以，可以
    //用两个栈进行操作，第一个栈正常操作，第二个栈做以辅助，用于保存最小的元素
    //
    template <class T>
    class TimeO1Stack
    {
    public:
    	/*TimeO1Stack()
    		:_s1(NULL)
    		, _s2(NULL)
    	{}
    
    	~TimeO1Stack()
    	{}*/
    
    public:
    	void Push(const T& x)
    	{
    		_s1.push(x);
    		if (!_s2.empty())
    		{
    			T tmp = _s2.top();
    			if (tmp > x)
    				_s2.push(x);
    
    		}
    		else
    			_s2.push(x);
    	}
    
    	void Pop()
    	{
    		T tmp = _s1.top();
    		_s1.pop();
    		
    		if (tmp == _s2.top())
    		{
    			_s2.pop();
    		}
    	}
    
    	T& Min()
    	{
    		return _s2.top();
    	}
    
    protected:
    	stack<T> _s1;
    	stack<T> _s2;
    };
    
    void TestTimeO1Stack()
    {
    	TimeO1Stack<int> s;
    	s.Push(1);
    	s.Push(2);
    	s.Push(3);
    	s.Push(4);
    	s.Pop();
    	cout << s.Min() << endl;;
    }</span>