Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
解题思路：
主要是取得当前最小值的问题。我们可以用1个动态数组min存储当前最小值。若新压入的元素大于动态数组min最后1个元素，不做任何操作。否则（小于或等于）就压入min中。出栈的时候，若出栈元素等于min最后1个元素，则min数组出栈。这样便实现了常量时间找到栈中的最小值了。下面是代码：
class MinStack {
public:
MinStack(){
capcity=2;
data = new int[capcity];
size=0;
minCapcity=2;
min = new int[minCapcity];
minSize = 0;
}
~MinStack(){
delete[] data;
delete[] min;
}
void push(int x) {
if(size>=capcity){
int* p=data;
capcity = 2*capcity;
data=new int[capcity];
std::memcpy(data, p, sizeof(int)*size);
delete[] p;
}
data[size++]=x;
if(minSize==0){
min[minSize++]=x;
}else if(min[minSize⑴]>=x){
if(minSize>=minCapcity){
int* p=min;
minCapcity = 2*minCapcity;
min = new int[minCapcity];
std::memcpy(min, p, sizeof(int)*minSize);
delete[] p;
}
min[minSize++]=x;
}
}
void pop() {
if(size>0){
size--;
if(data[size]==min[minSize⑴]){
minSize--;
}
}else{
throw exception();
}
}
int top() {
if(size>0){
return data[size⑴];
}else{
throw exception();
}
}
int getMin() {
return min[minSize⑴];
}
private:
int size;
int capcity;
int* min;
int minSize;
int minCapcity;
int* data;
};