3-最小栈

提示：pop、getMin和top操作总是在非空栈进行操作。

自己的做法

算法思想

使用链表来存储元素。

因为要求在常数时间内检索到最小元素的栈，所以肯定不能当调用getMin()时在栈中遍历元素。

应当是在push和pop操作中就需要找到最小值，当调用getMin()时直接返回。

因此我的思路是设置一个min指针，一直指向最小值。

算法实现

class MinStack {
private:
    typedef struct Node {
        int val;
        struct Node *next;
    } node;

    node *head = nullptr;
    node *min = nullptr;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int val) {
        node * temp = new node();
        temp->val = val;
        temp->next = head;
        head = temp;

        if(min == nullptr) {
            min = temp;
        } else {
            min = min->val < val ? min : temp;
        }
    }

    void pop() {
        if(head == nullptr) {
            return;
        }

        //如果最小值就是栈顶元素,则需要重新找最小值
        if(min == head) {
            //如果栈中只有一个元素或两个元素
            if(head->next == nullptr || head->next->next == nullptr) {
                min = head->next;
            } else { // 否则遍历链表，查找最小值
            min = head->next;
            node *temp = min->next;
            while (temp != nullptr) {
                    if(min->val > temp->val) {
                        min = temp;
                    }
                    temp = temp->next;
                }
            }
        }

        //删除栈顶元素
        node * top = head;
        head = head->next;
    }

    int top() {
        return head->val;
    }

    int getMin() {
        return min->val;

    }
};

性能分析

• 时间复杂度：push、top和getMin都是$O(1)$，pop操作最坏时间复杂度是$O(n)$。
• 空间复杂度：$O(1)$。

官方提供的做法

算法思想

使用辅助栈，每一个栈顶元素对应一个最小值。即在一个栈存放数据，另一个栈存放和数据栈对应位置的元素对应的最小值。

当向数据栈中添加元素时，比较当前辅助栈栈顶元素和插入元素大小，取较小的添加到辅助栈。

从数据栈中删除栈顶元素时，同时删除辅助栈栈顶元素。

算法实现

class MinStack {
private:
    stack<int> data_stack;
    stack<int> min_stack;

public:
    /** initialize your data structure here. */
    MinStack() {
        min_stack.push(INT_MAX);
    }

    void push(int val) {
        data_stack.push(val);
        min_stack.push(min(val, min_stack.top()));
    }

    void pop() {
        data_stack.pop();
        min_stack.pop();
    }

    int top() {
        return data_stack.top();
    }

    int getMin() {
        return min_stack.top();
    }
};

性能分析

• 时间复杂度：添加、删除、返回栈顶元素和返回最小值都是$O(1)$
• 空间复杂度：$O(N)$

其他做法

可以使用C++的pair关键词，把要存储的元素和对应的最小值放在一个元组中。这样就只需要使用一个栈。

也可以不使用提供的stack默认实现，自定义链表实现，在定义节点时，添加min字段，即每一个节点都对应一个数据和最小值。

思路都大同小异，只不过具体实现不同。