// 演算法：用兩個 std::vector 當堆疊。dataStack 存資料，minStack 存「到此為止的最小值」。
// Algorithm: two std::vectors as stacks. dataStack holds data; minStack holds the running min.
// push 推入 min(val, 目前最小)；pop 同時彈出兩者；getMin 回傳 minStack.back()。
// push stores min(val, current min); pop pops both; getMin returns minStack.back().

#include <vector>      // std::vector，可自動增長的動態陣列 / a dynamic, auto-growing array
#include <algorithm>   // std::min，回傳兩數中的較小者 / returns the smaller of two values

class MinStack {
private:
    std::vector<int> dataStack;   // 主堆疊：尾端就是頂端 / main stack; the back() is the top
    std::vector<int> minStack;    // 最小值堆疊：與主堆疊同步 / running-min stack, kept in sync

public:
    // 建構子：vector 預設為空，不需做額外初始化
    // Constructor: vectors default to empty, no extra setup needed
    MinStack() {}

    // 推入 val
    // Push val
    void push(int val) {
        dataStack.push_back(val);                 // push_back 把 val 加到尾端（頂端）/ append val to the back (top)
        // 若 minStack 為空，最小值就是 val；否則取 val 與目前最小值的較小者
        // If minStack is empty, the min is val; otherwise take min(val, current min)
        if (minStack.empty()) {
            minStack.push_back(val);              // 首個元素 / first element
        } else {
            minStack.push_back(std::min(val, minStack.back()));  // back() 是頂端 / back() is the top
        }
    }

    // 移除頂端
    // Remove the top
    void pop() {
        dataStack.pop_back();   // pop_back 移除尾端元素 / remove the back element
        minStack.pop_back();    // 兩個堆疊必須同步彈出 / both stacks must pop together
    }

    // 取得頂端元素
    // Get the top element
    int top() {
        return dataStack.back();   // back() 回傳尾端（頂端）元素 / back() returns the top element
    }

    // 取得目前最小值
    // Get the current minimum
    int getMin() {
        return minStack.back();    // minStack 頂端即最小值，O(1) / minStack's top is the min, O(1)
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */