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