155. Min Stack

操作：     MinStack(), push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
輸出：     null,       null,     null,    null,     -3,       null,  0,     -2

// 演算法：用兩個堆疊。dataStack 存實際資料，minStack 同步存「到目前為止的最小值」。
// Algorithm: two stacks. dataStack holds the data; minStack holds the running minimum.
// push 時把 min(val, 目前最小) 推入 minStack；pop 時兩者同時彈出，getMin 讀 minStack 頂端。
// On push, store min(val, current min) in minStack; pop both together; getMin reads minStack's top.

#include <stdlib.h>   // malloc / free / realloc，動態記憶體 / dynamic memory

// MinStack 結構：用兩個動態陣列模擬兩個堆疊
// The MinStack struct: two dynamic arrays acting as two stacks
typedef struct {
    int *data;     // 主堆疊的元素陣列 / array storing the main stack elements
    int *minv;     // 最小值堆疊的元素陣列 / array storing the running minimums
    int size;      // 目前堆疊有幾個元素（也是下一個寫入位置）/ current count = next write index
    int cap;       // 陣列目前能容納的容量 / current allocated capacity
} MinStack;

// 建立並初始化一個 MinStack 物件
// Create and initialize a MinStack object
MinStack* minStackCreate(void) {
    MinStack *s = (MinStack *)malloc(sizeof(MinStack));  // 配置結構本身的記憶體 / allocate the struct
    s->cap  = 16;                                        // 先給一個小的初始容量 / start with a small capacity
    s->size = 0;                                         // 一開始是空的 / initially empty
    s->data = (int *)malloc(sizeof(int) * s->cap);       // 配置主堆疊陣列 / allocate the data array
    s->minv = (int *)malloc(sizeof(int) * s->cap);       // 配置最小值堆疊陣列 / allocate the min array
    return s;                                            // 回傳指標供後續操作使用 / return the pointer
}

// 把 val 推入堆疊
// Push val onto the stack
void minStackPush(MinStack* obj, int val) {
    if (obj->size == obj->cap) {                         // 容量滿了就要擴充 / grow when array is full
        obj->cap *= 2;                                   // 容量加倍，分攤成本 O(1) / double capacity (amortized O(1))
        // realloc 把陣列搬到更大的空間，舊資料會保留 / realloc resizes the block, keeping old data
        obj->data = (int *)realloc(obj->data, sizeof(int) * obj->cap);
        obj->minv = (int *)realloc(obj->minv, sizeof(int) * obj->cap);
    }
    obj->data[obj->size] = val;                          // 把 val 寫到主堆疊頂端 / write val at the top of data
    // 計算新的最小值：若堆疊原本是空的，最小值就是 val；否則和前一個最小值比較取較小者
    // Compute new minimum: if empty, it's val; otherwise take min(val, previous min)
    if (obj->size == 0 || val < obj->minv[obj->size - 1]) {
        obj->minv[obj->size] = val;                      // val 更小（或首個元素），記錄 val / val is smaller (or first)
    } else {
        obj->minv[obj->size] = obj->minv[obj->size - 1]; // 沿用前一個最小值 / carry over previous min
    }
    obj->size++;                                         // 元素數量加一 / increment count
}

// 移除頂端元素
// Remove the top element
void minStackPop(MinStack* obj) {
    obj->size--;            // 只要把 size 減一，頂端就被「丟棄」了，無需清資料 / just decrement size to drop the top
}

// 取得頂端元素
// Get the top element
int minStackTop(MinStack* obj) {
    return obj->data[obj->size - 1];   // size-1 是頂端索引 / size-1 is the top index
}

// 取得目前最小值
// Get the current minimum
int minStackGetMin(MinStack* obj) {
    return obj->minv[obj->size - 1];   // minStack 頂端即為最小值，O(1) / minStack's top is the min, O(1)
}

// 釋放所有配置的記憶體，避免記憶體洩漏
// Free all allocated memory to avoid leaks
void minStackFree(MinStack* obj) {
    free(obj->data);    // 釋放主堆疊陣列 / free the data array
    free(obj->minv);    // 釋放最小值陣列 / free the min array
    free(obj);          // 釋放結構本身 / free the struct itself
}

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

// 演算法：用兩個 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();
 */