设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1) 设计一个栈和一个普通的数组，这个数组的大小和栈的大小一致，数组的每一位记录从栈底到当前为止的最小值，当新插入一个数时，只要比较这个数和之前栈中的最小值，把更小的放入数组中，当出栈时，数组中的值也相应出栈 栈 ： 8 3 3 4 8 2 1 4 0 数组： 8 3 3 3 3 2 1 1 0
一般定义的栈，若pop和push是O（1）,则求最小值时需要遍历栈，则复杂度是O（N）；
所以在栈类型实现当中，需要定义一个数组来记录最小值的出现顺序，也就是用空间复杂度换取时间复杂度：
代码的实现如下，主要用到了一个mystack动态数组操作普通的栈；一个 minstack数组栈顶用于记录最小的值：
#include
using namespace std;
#define mystack_empty -1
template
class _mystack{
public:
_mystack(int c, int i) :capacity(c),_top(i){
mystack = new T[capacity];
minstack = new T[capacity];
}
~_mystack()
{
delete[] mystack;
delete[] minstack;
}
void push(const T &t)
{
if (_top < capacity)
{
//入mystack栈
mystack[_top+1] = t;
//把比minstack栈顶元素小的指入栈到minstack中，
//minstack用于记录最小的元素；
if (_top<0 || minstack[_top]>t)
{
minstack[_top+1] = t;
}
else
{
//minstack的栈顶一直保持最小的值
minstack[_top + 1] = minstack[_top];
}
++_top;
}
//满栈
else
{
cout << "The Stack is Fulled!\n";
}
}
void pop()
{
if (_top >= 0)
{
_top--;
}
else
{
cout << "The Stack is Empty!\n";
}
}
T min()
{
if (_top >= 0)
{
return minstack[_top];
}
else
{
cout << "The minStack is Empty!\n";
return mystack_empty;
}
}
T top()
{
if (_top >= 0)
{
return mystack[_top];
}
else
{
cout << "The Stack is Empty!\n";
return mystack_empty;
}
}
private:
int capacity;
int _top;
T *mystack;
T *minstack;
};
int main(void)
{
_mystack
for (int i = 0; i < 10; ++i)
{
s.push(i);
}
cout << "top: "<< s.top() << endl;
s.pop();
cout << "top: "<< s.top() << endl;
cout << "min: "<< s.min() << endl;
return 0;
}
运行结果如下所示：
