1. 题目描述

problem link

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.

2. 解题

第一种方法，可以用两个栈解决这个问题，如下图：

左边的栈正常存储数据，右边的栈的每一个元素存储的是在正常栈中当前位置到栈底的区域内的最小值。

模拟一下这个过程，依次进栈7 3 5 4 1 9，压7的时候最小值是7所以右栈压7，压3的时候最小值是3所以压3，压5的时候最小值还是3所以右栈压3，依此类推，这样取最小值的时候直接取右栈栈顶元素就行了。

第二个方法，只用一个栈就解决这个问题（但用的空间并没有减少），相当于把上一个方法的两个栈合并成一个栈，每次插入一个元素，要往栈中压两个元素，一个正常元素一个最小元素，类似下图：

3. 代码

我的栈容量直接设置成10w，当然设成可扩容的模式更好。

两个栈：

typedef struct {
    int stack[100000];
    int minStack[100000];
    int top;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* p = (MinStack *)malloc(sizeof(MinStack));
    p->top = 0;

    return p;
}

void minStackPush(MinStack* obj, int x) {
    // 把这个数无脑压进普通栈
    obj->stack[obj->top] = x;

    // 把最小值压进最小栈
    if (obj->top == 0) {
        obj->minStack[obj->top] = x;
    }
    else {
        int min = obj->minStack[obj->top - 1];
        obj->minStack[obj->top] = x < min ? x : min;
    }

    // 增加top
    obj->top++;
}

void minStackPop(MinStack* obj) {
    obj->top--;
}

一个栈：

typedef struct {
    int minStack[100000];
    int top;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* p = (MinStack *)malloc(sizeof(MinStack));
    p->top = 0;

    return p;
}

void minStackPush(MinStack* obj, int x) {
    int min;

    if (obj->top == 0) {  // 空栈，直接入栈就可以了
        obj->minStack[obj->top] = x;
        obj->minStack[obj->top + 1] = x;
        obj->top += 2;
    }
    else {
        min = obj->minStack[obj->top - 1];  // 取出栈中最小元素
        obj->minStack[obj->top] = x;
        obj->minStack[obj->top + 1] = x < min ? x : min;
        obj->top += 2;
    }
}

void minStackPop(MinStack* obj) {
    obj->top -= 2;
}

int minStackTop(MinStack* obj) {
    return obj->minStack[obj->top - 2];
}

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

void minStackFree(MinStack* obj) {
    free(obj);
}