LeetCode – 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.

 

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

解题:

    与普通栈不同,增加了一个返回栈最小值的功能, 这里使用了两个栈, 一个保存数据 , 一个保存压栈过程中出现过的最小值。

         数据入栈,如果值大于等于当前最小值就入栈,注意这里的等于条件, 出最小值栈会判断是否与当前数据栈值一致,如果不增加等于条件, 会导致最小栈先于数据栈清空, 后续无法获取最小值。

          数据出栈时 ,在最小值栈中判断一下是否是当前最小值, 如果是,将最小值栈出栈。 

实现:



typedef struct {
    int *arr;
    int cnt;
    int *min;
    int mincnt;
    int limit;
    
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack));
    obj->limit = 8192;
    obj->arr = (int*) malloc(sizeof(int)*(obj->limit));
    obj->min = (int*) malloc(sizeof(int)*(obj->limit));
    obj->cnt =0;
    obj->mincnt =0;
    return obj;
}

void minStackPush(MinStack* obj, int x) {
    obj->arr[obj->cnt++] = x;
    if (obj->mincnt==0 || x <= obj->min[obj->mincnt-1]){
        obj->min[obj->mincnt++] = x;
    }
  
}

void minStackPop(MinStack* obj) {
    
    if ( obj->arr[obj->cnt-1] == obj->min[obj->mincnt-1] ){
        obj->mincnt--;
    }
    obj->cnt--;
  
}

int minStackTop(MinStack* obj) {
   return obj->arr[obj->cnt-1];
}

int minStackGetMin(MinStack* obj) {
  return obj->min[obj->mincnt-1];
}

void minStackFree(MinStack* obj) {
    free(obj->arr);
    free(obj->min);
    free(obj);
    return;
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注