C语言刷题 LeetCode 30天挑战 （十）Stack 栈 （MinStack）

这个题目要求你设计一个特殊的栈（MinStack），不仅要具备普通栈的基本功能（push、pop 和 top），还要能够在常数时间内（O(1) 时间复杂度）获取栈中的最小元素（getMin）。

基本栈操作如下：

• push(x)：将元素 x 压入栈顶。
• pop()：移除栈顶元素。
• top()：返回栈顶元素，但不移除它。
• getMin()：在常数时间内返回当前栈中最小的元素。

//Design a stack that supports push, pop, top, 
//and retrieving the minimum element in constant time
//push(x)-- Push element x onto stack.
//pop() --Removes the element on top of the stack.
//top() -- Get the top element.
//getMin()--Retrieve the minimum element in the stack.

//Minstack minstack = new Minstack();
//minstack.push(-2);
//minstack.push(0);
//minstack.push(-3);
//minstack.getMin();--> Returns -3.
//minstack.pop();
//minstack.top();--> Returns 0.
//minstack.getMin();--> Returns -2.

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

// 定义栈结构
typedef struct {
    int *stack;       // 存储所有元素的栈
    int *minStack;    // 辅助存储最小元素的栈
    int top;          // 主栈的栈顶指针
    int minTop;       // 最小栈的栈顶指针
    int capacity;     // 栈的容量
} Minstack;

// 创建 Minstack 并初始化
Minstack* minStackCreate() {
    Minstack* obj = (Minstack*)malloc(sizeof(Minstack));
    obj->capacity = 100;  // 假设初始容量为100
    obj->stack = (int*)malloc(sizeof(int) * obj->capacity);
    obj->minStack = (int*)malloc(sizeof(int) * obj->capacity);
    obj->top = -1;
    obj->minTop = -1;
    return obj;
}

// push 操作
void minstackPush(Minstack* obj, int x) {
    // 主栈操作
    obj->stack[++(obj->top)] = x;
    
    // 更新最小栈
    if (obj->minTop == -1 || x <= obj->minStack[obj->minTop]) {
        obj->minStack[++(obj->minTop)] = x;
    }
}

// pop 操作
void minstackPop(Minstack* obj) {
    if (obj->top == -1) return;  // 空栈
    int popped = obj->stack[obj->top--];  // 弹出主栈栈顶元素

    // 如果弹出的元素是当前最小值，也从 minStack 中弹出
    if (popped == obj->minStack[obj->minTop]) {
        obj->minTop--;
    }
}

// 获取栈顶元素
int minstackTop(Minstack* obj) {
    if (obj->top == -1) return -1;  // 空栈
    return obj->stack[obj->top];
}

// 获取栈中的最小元素
int minstackGetMin(Minstack* obj) {
    if (obj->minTop == -1) return -1;  // 空栈
    return obj->minStack[obj->minTop];
}

// 释放栈内存
void minstackFree(Minstack* obj) {
    free(obj->stack);
    free(obj->minStack);
    free(obj);
}

// 打印主栈和最小栈的内容
void printStack(Minstack* obj) {
    printf("Stack: ");
    if (obj->top == -1) {
        printf("Empty\n");
    } else {
        for (int i = 0; i <= obj->top; i++) {
            printf("%d ", obj->stack[i]);
        }
        printf("\n");
    }

    printf("MinStack: ");
    if (obj->minTop == -1) {
        printf("Empty\n");
    } else {
        for (int i = 0; i <= obj->minTop; i++) {
            printf("%d ", obj->minStack[i]);
        }
        printf("\n");
    }
}

int main() {
    Minstack* minstack = minStackCreate();
    
    minstackPush(minstack, -2);
    minstackPush(minstack, 9);
    minstackPush(minstack, -3);
    minstackPush(minstack, 1);
    minstackPush(minstack, 2);
    minstackPush(minstack, 3);

    printStack(minstack);  // 打印主栈和最小栈
    printf("getMin: %d\n", minstackGetMin(minstack));  // 返回 -3
    
    minstackPop(minstack);
    printStack(minstack);  // 打印主栈和最小栈

    printf("top: %d\n", minstackTop(minstack));        // 返回 0
    printf("getMin: %d\n", minstackGetMin(minstack));  // 返回 -2
    
    printStack(minstack);  // 打印主栈和最小栈
    minstackFree(minstack);  // 释放内存
    return 0;
}