面试经典150题——最小栈

​Life is a journey, there's no right or wrong.

1. 题目描述

2.  题目分析与解析

2.1 思路一

看到题目的一瞬间，有没有注意到 常数时间内检索到最小元素的栈，那说明我们肯定需要把最小元素的下标存储起来，这样才能在常数时间内找到。

其次因为它是一个栈，我们就需要定义一个数组，用来存储栈内元素。根据栈的 先进后出的性质，需要指定两个指针，用来指向栈的头和尾。

代码思路：

1. 定义一个数组，定义两个指针表示栈头尾，定义一个指针表示最小元素的

2. 初始化栈，初始大小及增长自定

3. push操作将元素加入数组，并将尾指针后移1，同时比较当前元素和最小元素大小，取出最小的那个元素的下标更新表示最小元素的的指针

4. pop操作将元素加入数组，并将尾指针前移1，同时比较pop的元素和最小元素大小，如果pop出的元素就是最小元素，那么遍历数组找到新的最小值存储在指针

5. top操作取出尾指针指向的元素

6. getMin直接返回最小元素下标的位置的值

7. 注意因为数组长度不能固定，需要在push和pop时动态变化大小

因为题目提示了：

，所以就直接定义数组为int类型。

（不瞒大家，因为两行代码的顺序问题搞了一上午用python生成了测试用例才找到原因，就在这里记录一下：

顺序问题啊，先拷贝再赋值，我之前先赋值再拷贝）

3. 代码实现

3.1 思路一

4. 相关复杂度分析

时间复杂度分析：

1. push(int val):

   • 扩容操作的时间复杂度为 O(N)，其中 N 是当前栈中的元素个数。因为在扩容时需要将原数组中的元素拷贝到新数组中。

   • 更新栈顶指针、更新最小值的操作为 O(1)。

2. pop():

   • 缩容操作的时间复杂度为 O(N)，其中 N 是当前栈中的元素个数。因为在缩容时需要将原数组中的元素拷贝到新数组中。

   • 查找新的最小值的操作为 O(N)，其中 N 是当前栈中的元素个数。因为需要遍历栈中的元素以找到最小值。

   • 更新栈顶指针的操作为 O(1)。

3. top() 和 getMin():

   • 这两个方法的时间复杂度都为 O(1)，因为它们只是简单地返回栈顶元素和当前最小值，没有涉及遍历或其他复杂操作。

因此，总体来说，push、pop 操作的时间复杂度取决于栈中元素的数量，并且可能会触发数组扩容和缩容，而这些操作的时间复杂度与元素数量成线性关系。

空间复杂度分析：

1. elements数组的空间复杂度：

   • 最初创建时，数组的长度是 10，因此空间复杂度为 O(1)。

   • 随着元素的增加、删除以及数组的扩容和缩容，数组的空间会动态变化，但总体上考虑，空间复杂度为 O(N)，其中 N 是栈中的元素个数。

综上所述，时间复杂度取决于元素的数量，而空间复杂度随着元素数量的增加而线性增加。