155. Min Stack

題目網址：https://leetcode.cn/problems/min-stack/

題意：設計一個支持 push、pop、top 操作, 並且能在 $O(1)$ time 得到最小元素的 stack。

實作 MinStack class：

• MinStack()：初始化 instance
• void push(int val)：將 val push 到 stack 中
• void pop()：移除 stack 頂端元素
• void top()：得到 stack 頂端元素
• int getMin()：得到 stack 中的最小元素

Solution：

想法：利用兩個 Stack, 其中 stack stk 紀錄元素 push / pop 的過程, 另一個 stack minStk.top() 紀錄每一次 push 元素到 stk 後, 當前 stk 中的的最小值

class MinStack {
public:
    MinStack() {
        // 讓 minStk 初始有一個最大值, 這樣後續 push 時 minStk 一定有 top 元素可比較
        minStk.emplace(INT_MAX);
    }

    void push(int val) {
        stk.emplace(val);
        minStk.emplace(min(minStk.top(), val)); // 新增元素後, 紀錄當前的最小元素
    }

    void pop() {
        stk.pop();
        minStk.pop();
    }

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

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

private:
    stack<int> stk;
    stack<int> minStk;
};

• time：皆為 $O(1)$
• space：$O(n)$ ➔ stk 的元素個數最多為 n, minStk 的元素個數最多為 n + 1