[LeetCode] Min Stack
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-04-20 08:18:05 閱讀次數(shù)：2656次
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.
解題思路：
主要是取得當(dāng)前最小值的問(wèn)題。我們可以用1個(gè)動(dòng)態(tài)數(shù)組min存儲(chǔ)當(dāng)前最小值。若新壓入的元素大于動(dòng)態(tài)數(shù)組min最后1個(gè)元素，不做任何操作。否則（小于或等于）就壓入min中。出棧的時(shí)候，若出棧元素等于min最后1個(gè)元素，則min數(shù)組出棧。這樣便實(shí)現(xiàn)了常量時(shí)間找到棧中的最小值了。下面是代碼：
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;
};
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
