这个题目要求你设计一个特殊的栈（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; // 假设初始容量为100obj->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)); // 返回 -3minstackPop(minstack);printStack(minstack); // 打印主栈和最小栈printf("top: %d\n", minstackTop(minstack)); // 返回 0printf("getMin: %d\n", minstackGetMin(minstack)); // 返回 -2printStack(minstack); // 打印主栈和最小栈minstackFree(minstack); // 释放内存return 0;
}
