思路:設定一個坐标loc_min指向最小的元素,然後每次入棧的時候比較入棧的元素是否為最小值。需要注意的一點是,出棧的時候需要考慮出棧的元素恰好為最小棧的情況。
ps:本題用數組來當作棧,空間複雜度可能不如寫好的stack好,因為數組不能動态擴容是以要盡量開的大一點。但是思路近似。
class MinStack {
public:
/** initialize your data structure here. */
int stack_int[100000];
int loc;
int min;
int min_loc;
MinStack()
{
loc=0;
min=0;
min_loc=0;
}
void push(int x)
{
stack_int[loc]=x;
loc++;
if(loc==1)
{
min=x;
min_loc=0;
}
else
{
if(x<min)
{
min=x;
min_loc=loc-1;
}
}
}
void pop()
{
loc--;
if(min_loc==loc&&loc>0)
{
min=stack_int[0];
min_loc=0;
for(int i=0;i<loc;i++)
{
if(stack_int[i]<min)
{
min=stack_int[i];
min_loc=i;
}
}
}
}
int top()
{
int loc_top=loc-1;
return stack_int[loc_top];
}
int getMin()
{
return stack_int[min_loc];
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/