155. 最小栈

难度：简单

题目

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

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

示例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

Reference

题解

基本思路： 使用两个域分别存储当前数值和当前栈中的最小值。

代码如下：

#define MIN(x, y) (x < y ? x : y)
struct cell
{
    int val;
    int curMin;
};
typedef struct {
    struct cell values[10000];
    int top;
} MinStack;
/** initialize your data structure here. */
MinStack *minStackCreate() 
{
    return (MinStack *)memset(malloc(sizeof(MinStack)), 0, sizeof(MinStack));
}
void minStackPush(MinStack* obj, int x)
{
    obj->values[obj->top].val = x;
    obj->values[obj->top].curMin = obj->top > 0 ? MIN(x, obj->values[obj->top - 1].curMin) : x;
    obj->top++;
}
void minStackPop(MinStack *obj)
{
    obj->top--;
}
int minStackTop(MinStack* obj)
{
    return obj->values[obj->top - 1].val;
}
int minStackGetMin(MinStack* obj)
{
    return obj->values[obj->top - 1].curMin;
}
void minStackFree(MinStack* obj)
{
    free(obj);
}
/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);

 * minStackPop(obj);

 * int param_3 = minStackTop(obj);

 * int param_4 = minStackGetMin(obj);

 * minStackFree(obj);
*/

评论