【栈】最小栈（LeetCode155）

红太狼 2022-10-13 15:47 134阅读 0赞

## 一、题目 ##

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    
    push(x) —— 将元素 x 推入栈中。
    pop() —— 删除栈顶的元素。
    top() —— 获取栈顶元素。
    getMin() —— 检索栈中的最小元素。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/min-stack
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

## 二、解析 ##

对于栈结构来说，具有天然的**先进后出**的性质。即如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。

因此我们无法直接获取栈中的最小元素，要实现getMin()，就必须新建一个栈min\_stack，将最小值存起来。这样我们就能直接通过top()来获取原栈的最小值。

对于其他的基本要求，比如push、pop、top都很简单，只需要在原栈上进行相应的操作即可。

## 三、实现 ##

根据以上的分析，采用C++实现如下：

/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
    
    class MinStack { 
        stack<int> mystack;
        stack<int> min_stack;
    public:
        /** initialize your data structure here. */
        MinStack() { 
            min_stack.push(INT_MAX);
        }
        
        void push(int val) { 
            mystack.push(val);
            min_stack.push(min(min_stack.top(), val));
        }
        
        void pop() { 
            mystack.pop();
            min_stack.pop();
        }
        
        int top() { 
            return mystack.top();
        }
        
        int getMin() { 
            return min_stack.top();
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/b55b2e3ddaed45e5a1cbf404bc54e652.png