[Daily]设计一个获取最小值时间复杂度为O(1)的栈

【题目】

• 实现一个栈，在实现栈的基本功能的前提下，再实现返回最小元素的操作。

【要求】

• pop、push、getMin操作的时间复杂度都是O(1)
• 设计的类可以使用现成的栈结构。

【分析】

• 想要使得获取最小值的时间复杂度为O(1),最简单的方法就是提前将最小值记录下来，当我们需要获取时便可直接获取
• 栈的特点就是先进后出。它的操作具有一定规律，这使得我们可以很好的记录最小值。
• 很容易就能够想到“双栈”来实现

【实现】

• 实现语言：C++
• 源代码如下：

#include<iostream>
#include<stack> 
using namespace std;#define Error -1// 一个有获取最小值功能的特殊栈，获取最小值的时间复杂度为O(1) 
class GetMinStack
{private:stack<int> m_BasicStack;                 //主栈stack<int> m_MinNumStack;                //最小值栈public:	void push(int value)                     //入栈{if(m_BasicStack.empty())            //如果栈中无数据m_MinNumStack.push(value);        else if(value<=m_MinNumStack.top())  //如果入栈的值比当前的最小值还要小m_MinNumStack.push(value);m_BasicStack.push(value); } int pop(){if(m_MinNumStack.empty()){//不可出栈cout<<"您操作的栈为空"<<endl;return Error; }int temp=m_BasicStack.top();m_BasicStack.pop();if(temp==m_MinNumStack.top())m_MinNumStack.pop();return temp;  }int getMin(){if(m_MinNumStack.empty()){//不可出栈cout<<"您操作的栈为空"<<endl;return Error;  }return m_MinNumStack.top();}
};int main()
{GetMinStack test;test.push(5);test.push(8);test.push(4);test.push(10);cout<<"该栈最小的数为："<<test.getMin()<<endl; 
}

• 运行截图