【LeetCode with C: A Series of Problem-Solving Techniques】-- min Stack

leetcode

xianyu 2024-10-11 18:39:28 ‧ 189 瀏覽

分享至

Description

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.

Answer & Explaining

#include <stdio.h> 
#include <stdlib.h> 

// 定義Stacknode結構
typedef struct StackNode {
    int val; // 節點值
    struct StackNode* next; // 指向 next node的指標
} StackNode;

//定義 minStack
typedef struct {
    StackNode* stack; // stack的指標
    StackNode* minStack; // 輔助stack的minStack指標
} MinStack;

// 創建新的節點
StackNode* createNode(int val) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode)); // 動態分配記憶體
    node->val = val; // 設定節點值
    node->next = NULL; // 初始化 next 指標
    return node; // 返回新節點
}

// 初始化 MinStack
MinStack* minStackCreate() {
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack)); // 分配記憶體
    obj->stack = NULL; // 初始化stack
    obj->minStack = NULL; // 初始化minStack
    return obj; // 返回minStack obj
}

// 將元素Push到minStack
void minStackPush(MinStack* obj, int val) {
    StackNode* node = createNode(val); // 創建新節點
    node->next = obj->stack; // 新節點指向Stack頂
    obj->stack = node; // 更新Stack頂端為新節點

    //  為空或是新的值小於等於minStack值
    if (obj->minStack == NULL || val <= obj->minStack->val) {
        StackNode* minNode = createNode(val); // 創建新節點
        minNode->next = obj->minStack; // 指向minStack
        obj->minStack = minNode; //更新minStack頂為新節點
    }
}

// 從minStack pop出元素
void minStackPop(MinStack* obj) {
    if (obj->stack == NULL) return; // 如果stack為空，直接返回

    int topVal = obj->stack->val; // 獲取頂端元素
    StackNode* temp = obj->stack; // 儲存當前節點到temp
    obj->stack = obj->stack->next; // 更新stack頂端為下個node
    free(temp); // 釋放temp的記憶體空間

    // 如果pop的值等於原本的minStack頂端值
    if (topVal == obj->minStack->val) {
        temp = obj->minStack; // 將temp儲存到minStack頂端node
        obj->minStack = obj->minStack->next; // 更新minStack node為下一個節點
        free(temp); // 釋放temp
    }
}

// 獲取頂minStack的top
int minStackTop(MinStack* obj) {
    if (obj->stack == NULL) return -1; // 為空則回傳-1
    return obj->stack->val; // 否則返回頂點元素
}

// 獲取最小值
int minStackGetMin(MinStack* obj) {
    if (obj->minStack == NULL) return -1; // 如果minStack為空則回傳-1
    return obj->minStack->val; // 否則回傳minStack頂部值，及最小值
}

// 釋放minStack空間
void minStackFree(MinStack* obj) {
    // 釋放Stack所有節點
    while (obj->stack != NULL) {
        StackNode* temp = obj->stack; // 將當前node存到temp
        obj->stack = obj->stack->next; // 更新stack為下個node
        free(temp); // 釋放temp記憶體
    }
    // 釋放minStack記憶體
    while (obj->minStack != NULL) {
        StackNode* temp = obj->minStack; // 儲存當前minStack到temp
        obj->minStack = obj->minStack->next; // 更新minStack頂點為next
        free(temp); // 釋放temp記憶體
    }
    free(obj); // 釋放obj
}

Testing

#include <stdio.h> 
#include <stdlib.h> 

// 定義Stacknode結構
typedef struct StackNode {
    int val; // 節點值
    struct StackNode* next; // 指向 next node的指標
} StackNode;

//定義 minStack
typedef struct {
    StackNode* stack; // stack的指標
    StackNode* minStack; // 輔助stack的minStack指標
} MinStack;

// 創建新的節點
StackNode* createNode(int val) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode)); // 動態分配記憶體
    node->val = val; // 設定節點值
    node->next = NULL; // 初始化 next 指標
    return node; // 返回新節點
}

// 初始化 MinStack
MinStack* minStackCreate() {
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack)); // 分配記憶體
    obj->stack = NULL; // 初始化stack
    obj->minStack = NULL; // 初始化minStack
    return obj; // 返回minStack obj
}

// 將元素Push到minStack
void minStackPush(MinStack* obj, int val) {
    StackNode* node = createNode(val); // 創建新節點
    node->next = obj->stack; // 新節點指向Stack頂
    obj->stack = node; // 更新Stack頂端為新節點

    //  為空或是新的值小於等於minStack值
    if (obj->minStack == NULL || val <= obj->minStack->val) {
        StackNode* minNode = createNode(val); // 創建新節點
        minNode->next = obj->minStack; // 指向minStack
        obj->minStack = minNode; //更新minStack頂為新節點
    }
}

// 從minStack pop出元素
void minStackPop(MinStack* obj) {
    if (obj->stack == NULL) return; // 如果stack為空，直接返回

    int topVal = obj->stack->val; // 獲取頂端元素
    StackNode* temp = obj->stack; // 儲存當前節點到temp
    obj->stack = obj->stack->next; // 更新stack頂端為下個node
    free(temp); // 釋放temp的記憶體空間

    // 如果pop的值等於原本的minStack頂端值
    if (topVal == obj->minStack->val) {
        temp = obj->minStack; // 將temp儲存到minStack頂端node
        obj->minStack = obj->minStack->next; // 更新minStack node為下一個節點
        free(temp); // 釋放temp
    }
}

// 獲取頂minStack的top
int minStackTop(MinStack* obj) {
    if (obj->stack == NULL) return -1; // 為空則回傳-1
    return obj->stack->val; // 否則返回頂點元素
}

// 獲取最小值
int minStackGetMin(MinStack* obj) {
    if (obj->minStack == NULL) return -1; // 如果minStack為空則回傳-1
    return obj->minStack->val; // 否則回傳minStack頂部值，及最小值
}

// 釋放minStack空間
void minStackFree(MinStack* obj) {
    // 釋放Stack所有節點
    while (obj->stack != NULL) {
        StackNode* temp = obj->stack; // 將當前node存到temp
        obj->stack = obj->stack->next; // 更新stack為下個node
        free(temp); // 釋放temp記憶體
    }
    // 釋放minStack記憶體
    while (obj->minStack != NULL) {
        StackNode* temp = obj->minStack; // 儲存當前minStack到temp
        obj->minStack = obj->minStack->next; // 更新minStack頂點為next
        free(temp); // 釋放temp記憶體
    }
    free(obj); // 釋放obj
}

int main() {
    MinStack* minStack = minStackCreate(); //創建minStack
    minStackPush(minStack, -2); // push -2
    minStackPush(minStack, 0); // push 0
    minStackPush(minStack, -3); // push -3
    printf("%d\n", minStackGetMin(minStack)); // 输出目前最小值 -3
    minStackPop(minStack); // pop minStack頂端元素
    printf("%d\n", minStackTop(minStack)); // 输出目前頂端元素
    printf("%d\n", minStackGetMin(minStack)); // 輸出目前最小值
    minStackFree(minStack); // 釋放minStack
    return 0; 
}