每日一题——包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

• push(value)：将 value 压入栈中
• pop()：弹出栈顶元素
• top()：获取栈顶元素
• min()：获取栈中最小元素

数据范围：

• 操作数量满足 $0\le n\le 300$
• 输入的元素满足 $|val|\le 10000$
• 进阶：栈的各个操作的时间复杂度是 $O(1)$，空间复杂度是 $O(n)$

示例

输入：

["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出：

-1, 2, 1, -1

解析：

• "PSH-1"表示将-1压入栈中，栈中元素为-1
• "PSH2"表示将2压入栈中，栈中元素为2, -1
• "MIN"表示获取此时栈中最小元素==>返回-1
• "TOP"表示获取栈顶元素==>返回2
• "POP"表示弹出栈顶元素，弹出2，栈中元素为-1
• "PSH1"表示将1压入栈中，栈中元素为1, -1
• "TOP"表示获取栈顶元素==>返回1
• "MIN"表示获取此时栈中最小元素==>返回-1

C语言代码实现

#define MAX_SIZE 300  // 假设栈最大容量
int stack[MAX_SIZE]; // 定义一个整数数组作为栈的存储空间
int count = -1;      // 用于记录栈中元素的数量

// 压入栈中的值
void push(int value) {
    if (count < MAX_SIZE - 1) {
        stack[++count] = value;
    } else {
        printf("Stack is full.\n");
        return;
    }
}

// 弹出栈顶元素
void pop() {
    if (count == -1) {
        printf("Stack is empty.\n");
        return;
    }
    count--;
}

// 获取栈顶元素
int top() {
    if (count == -1) {
        return -1;
    }
    return stack[count];  // 返回栈顶元素的值
}

// 获取栈中最小的元素
int min() {
    if (count == -1) {
        return -1;
    }
    int minVal = stack[0]; 
    for (int i = 1; i <= count; i++) {
        minVal = (minVal > stack[i]) ? stack[i] : minVal;
    }
    return minVal;
}

解释

1. push(value)

该函数负责将一个元素压入栈中。当栈未满时，将元素存入 stack 数组，并将栈顶指针 count 增加。

2. pop()

该函数负责弹出栈顶元素。当栈不为空时，栈顶元素被移除，栈顶指针 count 减少。

3. top()

该函数返回栈顶的元素。如果栈为空，返回 -1，否则返回栈顶的值。

4. min()

该函数遍历整个栈，找到最小的元素并返回。如果栈为空，返回 -1。

总结

这题整体上还是很简单的，本以为是用大小堆实现的，没想到直接一个遍历就搞完了。明天研究一下如何用大小堆实现。

大小堆

GPT给的原始代码

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param value int整型
 * @return 无
 */
#define MAX_SIZE 300  // 假设栈最大容量，定义栈的最大大小为300
int stack[MAX_SIZE]; // 定义一个整数数组作为栈的存储空间
int count = -1; // 用于记录栈中元素的数量，初始化时栈为空
int data[MAX_SIZE]; // 用于存储堆的数据
int size = 0; // 堆中的元素数量，初始化时堆为空

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param 无
 * @return 无
 */
void insertMinHeap(int value) {
    int i = size++;  // 先将堆的大小增加1，并记录当前堆中元素的位置
    data[i] = value; // 将新元素插入堆的末尾
    // 将新插入的元素与其父节点比较并进行交换，直到堆的性质得到维护
    while (i > 0 && data[i] < data[(i - 1) / 2]) { 
        int temp = data[i];  // 交换操作的中间变量
        data[i] = data[(i - 1) / 2];  // 将父节点值移到当前节点
        data[(i - 1) / 2] = temp;  // 当前节点的值移到父节点
        i = (i - 1) / 2;  // 更新索引，继续与父节点比较
    }
}

// 堆的操作：删除堆顶元素
void removeMinHeap() {
    if (size == 0) return; // 如果堆为空，直接返回
    data[0] = data[--size]; // 用堆的最后一个元素替代堆顶元素
    // 维护堆的性质，逐步下沉替代后的堆顶元素
    int i = 0; 
    while (2 * i + 1 < size) {  // 判断当前节点是否有子节点
        int left = 2 * i + 1;  // 左子节点的索引
        int right = 2 * i + 2; // 右子节点的索引
        int smallest = i;  // 假设当前节点为最小元素

        if (left < size && data[left] < data[smallest]) {  // 如果左子节点小于当前节点
            smallest = left;  // 更新最小值的索引
        }
        if (right < size && data[right] < data[smallest]) {  // 如果右子节点小于当前节点
            smallest = right;  // 更新最小值的索引
        }

        if (smallest == i) break;  // 如果当前节点已经是最小的，结束循环

        // 交换当前节点与最小子节点
        int temp = data[i];
        data[i] = data[smallest];
        data[smallest] = temp;

        // 更新索引，继续下沉操作
        i = smallest;
    }
}

// 堆的操作：获取堆顶元素
void removeValueFromMinHeap(int value) {
    // 查找堆中要删除的值的索引
    int index = -1;
    for (int i = 0; i < size; i++) {
        if (data[i] == value) {
            index = i;  // 找到对应的索引
            break;
        }
    }
    
    // 如果没有找到该值，则返回
    if (index == -1) {
        printf("Value %d not found in heap.\n", value);
        return;
    }

    // 用堆的最后一个元素替换要删除的元素
    data[index] = data[--size];

    // 从替换位置开始调整堆
    int i = index;
    while (2 * i + 1 < size) {  // 判断当前节点是否有子节点
        int left = 2 * i + 1;  // 左子节点的索引
        int right = 2 * i + 2; // 右子节点的索引
        int smallest = i;  // 假设当前节点为最小元素

        // 找到较小的子节点
        if (left < size && data[left] < data[smallest]) {
            smallest = left;
        }
        if (right < size && data[right] < data[smallest]) {
            smallest = right;
        }

        // 如果当前节点已经是最小的，就不需要调整了
        if (smallest == i) break;

        // 交换当前节点与最小子节点
        int temp = data[i];
        data[i] = data[smallest];
        data[smallest] = temp;

        // 更新索引，继续调整下去
        i = smallest;
    }
}

// 从栈中弹出一个元素
void pop() {
    if (count == -1) {  // 如果栈为空，打印提示信息并返回
        printf("Stack is empty.\n");
        return;
    }
    int value = stack[count--];  // 取出栈顶元素并更新栈的计数器

    // 删除堆中的该值
    removeValueFromMinHeap(value);
}

// 返回栈顶元素
int top() {
    return stack[count];  // 返回栈顶元素的值
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param 无
 * @return int整型
 */
int min() {
    // 返回堆顶元素，也就是最小值
    return size > 0 ? data[0] : -1;  // 如果堆不为空，返回堆顶元素；否则返回-1
}

// 向栈中推入一个新元素
void push(int value) {
    if (count < MAX_SIZE - 1) {  // 判断栈是否已满
        stack[++count] = value;  // 将元素推入栈
        insertMinHeap(value);  // 将元素插入最小堆
    } else {
        printf("Stack is full.\n");  // 如果栈满了，打印提示信息
    }
}

通过结合栈和最小堆的操作，我们能够实现一个高效的栈结构，在常见的栈操作上（如压栈、弹栈）同时保证能够快速查询栈中的最小元素。一个栈用来存储数据，一个大小堆用来排序
最难的还是栈里面删除，大小堆已经排序过后必须找到特定的删除。挺难解决的。