Pure C impl. | Beats 98%
Note\n\nTry to utilize caching. Because push() accesses both member val and min. It would be better to put them near to each other.\n\n\n// A: Contiguous memory
# Note\n\nTry to utilize caching. Because `push()` accesses both member `val` and `min`. It would be better to put them near to each other.\n\n```\n// A: Contiguous memory\ntypedef struct {\n    int val;\n    int min;\n} data_t;\n\ndata_t *buf;\n\n// B: Not-contiguous memory\nint *val;\nint *min;\n```\n\n# Intuition\n\nTry to add operation `getMin()` with complexity $O(1)$ into stack.\n\n# Approach\n\n`getMin(0..n)` can be pre-caculated from the result `getMin(0..m-1)` and `val[n]`. We can use extra $O(n)$ space to store `getMin(0..n)` for every element, the directly access the value when `getMin()` is called.\n\n# Complexity\n- Time complexity: \n    - Amortized $O(1)$ for arbitrary length input sequence. (Extending array size needs $O(n)$ but it\'s not frequently happened.)\n    - $O(1)$ when allocating large enough memory during initialization\n\n- Space complexity: $O(n)$\n\n# Code\n```\n\ntypedef struct {\n    int val;\n    int min;\n} data_t;\n\ntypedef struct {\n    int capacity;\n    int size;\n    data_t *buf;\n} MinStack;\n\n#define min(a, b) ({ \\\n    __typeof__(a) _a = a; \\\n    __typeof__(b) _b = b; \\\n    (_a < _b) ? _a : _b; \\\n})\n\nMinStack* minStackCreate() {\n    MinStack* obj = malloc(sizeof(MinStack));\n    const int capacity = 30000;\n\n    obj->capacity = capacity;\n    obj->size = 0;\n    obj->buf = (data_t *)malloc(sizeof(*obj->buf) * (capacity + 1)) + 1;\n    obj->buf[-1].min = INT_MAX;\n    \n    return obj;\n}\n\nstatic void minStackResize(MinStack* obj, int size) {\n    obj->capacity = size;\n    obj->buf = (data_t *)realloc(obj->buf - 1, sizeof(*obj->buf) * (size + 1)) + 1;\n}\n\nvoid minStackPush(MinStack* obj, int val) {\n    if (obj->size == obj->capacity)\n        minStackResize(obj, obj->capacity << 1);\n    \n    const int idx = obj->size;\n    obj->size++;\n    obj->buf[idx] = (data_t){ .val = val, .min = min(val, obj->buf[idx-1].min) };\n}\n\nvoid minStackPop(MinStack* obj) {\n    obj->size--;\n}\n\nint minStackTop(MinStack* obj) {\n    return obj->buf[obj->size-1].val;\n}\n\nint minStackGetMin(MinStack* obj) {\n    return obj->buf[obj->size-1].min;\n}\n\nvoid minStackFree(MinStack* obj) {\n    free(obj->buf - 1);\n\n    obj->buf = NULL;\n    free(obj);\n}\n\n/**\n * Your MinStack struct will be instantiated and called as such:\n * MinStack* obj = minStackCreate();\n * minStackPush(obj, val);\n \n * minStackPop(obj);\n \n * int param_3 = minStackTop(obj);\n \n * int param_4 = minStackGetMin(obj);\n \n * minStackFree(obj);\n*/\n```
['C']