【栈】栈的最小值（面试题 03）

末蓝、 2022-10-18 15:49 166阅读 0赞

## 一、题目 ##

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
    执行push、pop和min操作的时间复杂度必须为O(1)。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/min-stack-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

## 二、分析 ##

我们都知道，对于栈来说，没有现成的函数getMin()来实现获取栈中元素的最小值。为此，需要我们自己来实现一个getMin()。当然，简单的做法是：遍历栈中的元素，通过比较来获取栈中元素的最小值，这样一来，时间复杂度就是O(n)。

对于本题而言，需要保证getMin()的时间复杂度必须为O(1)，所以以上方法不可取。本着空间换时间的基本思想，我们可以创建一个辅助栈min\_stack，来存储最小值，并始终放在栈顶。这样就可以直接通过min\_stack.top()来直接获取栈的最小值，时间复杂度满足O(1)的要求！

## 三、题解 ##

根据以上的分析，通过C++实现如下：

class MinStack { 
    public:
        /** initialize your data structure here. */
        stack<int> x_stack;
        stack<int> min_stack;
        
        MinStack() {  
           min_stack.push(INT_MAX);
        }
        
        void push(int x) { 
            x_stack.push(x);
            min_stack.push(min(min_stack.top(),x));
        }
        
        void pop() { 
            x_stack.pop();
            min_stack.pop();
        }
        
        int top() { 
            return x_stack.top();
        }
        
        int getMin() { 
            return min_stack.top();
        }
    };

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