C语言实现O(1)获取最小值的栈：双栈辅助设计

一、设计思路与目标

本题的目标是定义一种特殊的栈结构，使其在支持标准数据进出的同时，能够以常数时间复杂度 O(1) 返回栈中的最小值。由于普通栈的 push() 和 pop() 已满足 O(1)，难点仅在于优化 min() 函数。

核心原理

我们采用双栈辅助策略：

• 栈1（主栈）：负责存储所有正常的数据元素，保持标准的入栈、出栈、取栈顶行为。
• 栈2（辅助栈）：其栈顶元素永远对应当前栈1中的最小值。通过维持这一单调性，min() 只需直接读取栈2的栈顶即可。

第1步：初始化双栈结构

目的：构建内存容器，准备存放主数据和辅助极值。 入口：创建对象实例。
动作：使用动态内存分配（malloc）为栈1和栈2申请连续的空间，并将两个栈的指针变量（top1、top2）初始化为-1，表示栈空。
参数：设定合理的最大容量上限（如20000），防止越界访问。

第2步：处理入栈 push(x)

目的：更新数据集并同步最小值状态。 入口：push 函数调用。 动作：
1. 主栈操作：将新元素 x 放入栈1，指针 top1 加1。 2. 辅助栈决策：
- 若栈2为空，直接将 x 压入栈2（此时它就是首个最小值）。 - 若栈2不为空，比较 x 与栈2当前栈顶（现有最小值）的大小。 - 只有当 x 小于或等于栈2栈顶时，才将 x 压入栈2；否则不压入，保留原有的较小值。 完成状态：栈1包含 x，栈2顶端保证是当前所有入栈元素中的最小值。

第3步：处理出栈 pop()

目的：移除最新元素并恢复前序最小值。 入口：pop 函数调用。 动作：
1. 记录栈1当前的栈顶元素为 y，并将 top1 减1，完成主栈弹出。 2. 检查弹出的元素 y 是否等于栈2的当前栈顶元素。如果相等，说明刚才移除的正是当前的全局最小值，必须同时从栈2中弹出该元素（top2 减1），使辅助栈回归到上一个次小值状态。 风险提示：必须在栈非空状态下执行此操作。

第4步：查询 top() 与 min()

目的：快速获取关键数据。 动作： - top()：直接返回栈1索引 top1 处的数值。 - min()：直接返回栈2索引 top2 处的数值。 结果：两者均无需循环遍历，严格保持 O(1) 的访问速度。

二、C语言代码实现

以下代码基于 LeetCode 接口规范编写，使用静态数组分配方式管理内存。定义了一个结构体 MinStack 封装两个整型指针及对应的栈顶索引。

#define N 20000

//创建两个栈，栈1用于正常的入栈出栈操作，栈2用于将栈1的最小元素防在栈顶
typedef struct {
    int *Stack1;
    int *Stack2;
    int top1;
    int top2;
} MinStack;

/** initialize your data structure here. */
MinStack* minStackCreate() {
    MinStack* MS=(MinStack*)malloc(sizeof(MinStack));
    MS->Stack1 = (int*)malloc(sizeof(int)*N);
    MS->Stack2 = (int*)malloc(sizeof(int)*N);
    MS->top1 = -1;
    MS->top2 = -1;
    return MS;
}

void minStackPush(MinStack* obj, int x) {
    obj->Stack1[++obj->top1] = x; //栈1正常入栈
    if(obj->top2 == -1){   //如果栈2是空的
        obj->Stack2[++obj->top2] = x; //将x也压入栈2
    }
    else{
        //如果栈2不空，同时x<=栈2的栈顶元素
        if(x <= obj->Stack2[obj->top2]){
            //将x压入栈2的栈顶
            obj->Stack2[++obj->top2] = x;
        }
    }
}

void minStackPop(MinStack* obj) {
    //保存栈1的栈顶元素，同时top1-1
    int a = obj->Stack1[obj->top1];
    obj->top1--;
    //如果栈1的栈顶元素等于栈2的栈顶元素，则将栈2的栈顶元素弹出，top2-1
    if(a==obj->Stack2[obj->top2]){
        obj->top2--;
    }
}

//正常返回栈1的栈顶元素即可
int minStackTop(MinStack* obj) {
    return obj->Stack1[obj->top1];
}

//正常返回栈2的栈顶元素即可
int minStackMin(MinStack* obj) {
    return obj->Stack2[obj->top2];
}

void minStackFree(MinStack* obj) {
    free(obj->Stack1);
    free(obj->Stack2);
    free(obj);
}

三、功能验证与总结

上述结构实现了题目要求的所有接口。在实际应用中，当执行一系列入栈和出栈操作后，辅助栈会智能地维护最小值序列。例如，先推入 -2，再推入 0，最后推入 -3 时，栈2也会依次存入这三个数，此时 min() 返回栈2栈顶的 -3。弹出 0 后，栈1回到 0，栈2也弹出一层，再次调用 min() 则能正确返回 -2。

本方案利用空间换时间的思想，以额外的数组存储代价换取了极值查询的极致性能，适合频繁查询最小值的业务场景。以上就是C语言实现O(1)获取最小值栈的详细解析，更多关于LeetCode经典算法实战的资料请关注本站其它相关文章！