LeetCode题目（Python实现）：最小栈

小咪咪 2023-07-16 11:58 105阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：辅助栈
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

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

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

**示例** :

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

## 想法一：辅助栈 ##

### 算法实现 ###

class MinStack:
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.minStack = []
            self.stack = []
    
        def push(self, x: int) -> None:
            if not len(self.minStack) or self.minStack[- 1] >= x:
                self.minStack.append(x)
            self.stack.append(x)
    
        def pop(self) -> None:
            temp = self.stack.pop()
            if temp == self.getMin():
                self.minStack.pop()
    
        def top(self) -> int:
            return self.stack[- 1]
    
        def getMin(self) -> int:
            return self.minStack[- 1]

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 68 ms, 在所有 Python3 提交中击败了77.21%的用户  
**内存消耗** : 16.6 MB, 在所有 Python3 提交中击败了5.10%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(1)，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只有有限个步骤，因此时间复杂度是：O(1)。
 *  空间复杂度：O(N)，这里 N 是读出的数据的个数。

## 小结 ##

由于以前做过的原因，所以很快想到了辅助栈的方法，用的是优化过的数据栈和辅助栈不同步的方法，只在辅助栈中放入当前最小的元素，出栈时相同。

刚开始写的时候忘记了Python索引`-1`这个利器，还去用一个变量去维护栈元素的数量，之后看题解才想起来，果然Python太强大了，代码简洁，功能强大=。=

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/a5ca1f16780749bda546125be290a480.png