【面试题】剑指offer21--求栈里面的最小的数字

傷城~ 2022-06-13 06:13 112阅读 0赞

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素min函数。

在该栈中，调用min，push以及pop的时间复杂度都是O(1)。

首先，我们想到的方法是，在每一次入栈的时候比较一下，把小的数字放到上边，最后就可以得到最小的数字了。

但是这种方法就不能保证最先入栈的数字最后出栈，不符合栈的规则了。

于是我们想到了另外一种方法：

首先往空的数据栈里面压入一个数字5，现在最小的数字是5，我们将这个最小的数字也压入辅助栈。

接下来压入3，由于3小于之前的5，于是我们往辅助栈里面的数字更新为3。

继续往栈里面压入数字6，由于6大于之前的3，辅助栈里面压入的还是3。

继续也如数字2，由于2小于3，则辅助栈里面的数字更新为2。

再压入一个数字1，由于1小于2，辅助栈的数字更新为1。

于是最小的数字就是1。

![Center][]

使用代码实现：

#include<iostream>
    using namespace std;
    #include<stack>
    #include<assert.h>
    template<typename T>
    
    class StackWithMin
    {
    public:
    	void Push(const T& data)
    	{
    		s_Elem.push(data);
    		if (s_Min.empty() || data < s_Min.top())
    		{
    			s_Min.push(data);
    		}
    		else
    		{
    			s_Min.push(s_Min.top());
    		}
    	}
    	void Pop()
    	{
    		assert(!s_Min.empty() && !s_Elem());
    		s_Min.pop();
    		s_Elem.pop();
    	}
    
    	const T& Min()const
    	{
    		return s_Min.top();
    	}
    protected:
    	stack<T> s_Elem;
    	stack<T> s_Min;
    };

[Center]: /images/20220613/8731776f5c214f48b4354dde3a90c3c9.png