[LeetCode] Min Stack
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.
解题思路：
主要是获得当前最小值的问题。我们可以用一个动态数组min存储当前最小值。若新压入的元素大于动态数组min最后一个元素，不做任何操作。否则（小于或等于）就压入min中。出栈的时候，若出栈元素等于min最后一个元素，则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-1]>=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-1]){
minSize--;
}
}else{
throw exception();
}
}
int top() {
if(size>0){
return data[size-1];
}else{
throw exception();
}
}
int getMin() {
return min[minSize-1];
}
private:
int size;
int capcity;
int* min;
int minSize;
int minCapcity;
int* data;
};
二次刷题（2015-08-05）
同样的思路。注意min栈存储的是一个递减序列，栈顶是当前栈中最小的值。这样，每个操作其实都能够在常量时间完成。
class MinStack {
public:
void push(int x) {
ss.push(x);
if(min.empty() || x<=min.top()){
min.push(x);
}
}
void pop() {
int x = ss.top();
ss.pop();
if(x==min.top()){
min.pop();
}
}
int top() {
return ss.top();
}
int getMin() {
return min.top();
}
private:
stack min;
stack ss;
};
转载请注明： » [LeetCode] Min Stack
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
请登录后发表评论
登录
全部评论
