当前位置：首页 > article >正文

【C++】每日一题 219 最小栈

article 2024/12/22 17:28:33

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

C++实现：

#include <stack>

class MinStack {
private:
    std::stack<int> mainStack;
    std::stack<int> minStack;

public:
    MinStack() {
        
    }

    void push(int val) {
        mainStack.push(val);
        if (minStack.empty() || val <= getMin()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (mainStack.top() == getMin()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    int top() {
        return mainStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

在这个实现中，我们使用了两个栈：mainStack 用于存储元素，minStack 用于存储当前栈中的最小元素。

在 push 操作中，我们将元素推入 mainStack 中，并且判断该元素是否比当前最小元素小或等于最小元素，如果是，则将该元素也推入 minStack 中。
在 pop 操作中，我们先判断要删除的元素是否为当前最小元素，如果是，则同时从 mainStack 和 minStack 中删除该元素。
top 操作直接返回 mainStack 的栈顶元素。
getMin 操作直接返回 minStack 的栈顶元素，即当前栈中的最小元素。
这样，通过维护一个辅助栈来保存当前栈中的最小元素，我们可以在常数时间内检索到最小元素，同时支持常见的栈操作。

因为C++有stack数据结构，所以相对C语言逻辑较易实现，这里也给出C语言的两种实现

链表实现

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

typedef struct Node {
    int val;
    int minVal;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} MinStack;

MinStack* minStackCreate() {
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack));
    obj->top = NULL;
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    
    if (obj->top == NULL || val < obj->top->minVal) {
        newNode->minVal = val;
    } else {
        newNode->minVal = obj->top->minVal;
    }
    
    newNode->next = obj->top;
    obj->top = newNode;
}

void minStackPop(MinStack* obj) {
    if (obj->top == NULL) {
        return;
    }
    
    Node* temp = obj->top;
    obj->top = obj->top->next;
    free(temp);
}

int minStackTop(MinStack* obj) {
    if (obj->top == NULL) {
        return -1; // 栈为空时返回特定值
    }
    return obj->top->val;
}

int minStackGetMin(MinStack* obj) {
    if (obj->top == NULL) {
        return -1; // 栈为空时返回特定值
    }
    return obj->top->minVal;
}

void minStackFree(MinStack* obj) {
    while (obj->top != NULL) {
        Node* temp = obj->top;
        obj->top = obj->top->next;
        free(temp);
    }
    free(obj);
}

int main() {
    MinStack* obj = minStackCreate();
    minStackPush(obj, -2);
    minStackPush(obj, 0);
    minStackPush(obj, -3);
    
    printf("Min element: %d\n", minStackGetMin(obj)); // Output: -3
    
    minStackPop(obj);
    
    printf("Top element: %d\n", minStackTop(obj)); // Output: 0
    
    printf("Min element: %d\n", minStackGetMin(obj)); // Output: -2
    
    minStackFree(obj);
    
    return 0;
}

使用结构体 Node 表示链表节点，每个节点包含元素值 val、当前节点及之前节点中的最小值 minVal，以及指向下一个节点的指针 next。MinStack 结构体中只包含一个指针 top 指向栈顶节点。

通过在节点中记录当前节点及之前节点中的最小值，我们可以实现在常数时间内检索最小元素的功能。

数组实现

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

typedef struct {
    int *stack;
    int *minStack;
    int top;
} MinStack;

MinStack* minStackCreate() {
    MinStack *obj = (MinStack*)malloc(sizeof(MinStack));
    obj->stack = (int*)malloc(10000 * sizeof(int)); // 假设栈最大容量为 10000
    obj->minStack = (int*)malloc(10000 * sizeof(int));
    obj->top = -1;
    
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    obj->top++;
    obj->stack[obj->top] = val;
    
    if(obj->top == 0 || val <= obj->minStack[obj->top - 1]) {
        obj->minStack[obj->top] = val;
    } else {
        obj->minStack[obj->top] = obj->minStack[obj->top - 1];
    }
}

void minStackPop(MinStack* obj) {
    obj->top--;
}

int minStackTop(MinStack* obj) {
    return obj->stack[obj->top];
}

int minStackGetMin(MinStack* obj) {
    return obj->minStack[obj->top];
}

void minStackFree(MinStack* obj) {
    free(obj->stack);
    free(obj->minStack);
    free(obj);
}

int main() {
    MinStack* obj = minStackCreate();
    minStackPush(obj, -2);
    minStackPush(obj, 0);
    minStackPush(obj, -3);
    
    printf("Min element: %d\n", minStackGetMin(obj)); // Output: -3
    
    minStackPop(obj);
    
    printf("Top element: %d\n", minStackTop(obj)); // Output: 0
    
    printf("Min element: %d\n", minStackGetMin(obj)); // Output: -2
    
    minStackFree(obj);
    
    return 0;
}