[LeetCode] Min Stack
來源:程序員人生 發布時間:2015-04-20 08:18:05 閱讀次數:2671次
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;
};
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈