每日leetcode——155. 最小栈数据结构与算法

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

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

思路辅助栈 【每日leetcode——155. 最小栈】题目要求在常熟时间内能检索到最小元素，常数时间就是O(1)时间复杂度，因此不能使用for循环遍历检索，for循环的时间复杂度是O(n)
思路是再维护一个辅助栈 minStack, 让辅助栈的栈顶，始终保存的是当前栈中的最小元素

class MinStack:def __init__(self): # 普通栈 self.stack = [] # 辅助栈，初始化给一个无穷大 self.min_stack = [math.inf]def push(self, val: int) -> None: # 普通栈正常push self.stack.append(val) # 辅助栈只push小于等于栈顶的 self.min_stack.append(min(val,self.min_stack[-1]))def pop(self) -> None: self.stack.pop() self.min_stack.pop()def top(self) -> int: return self.stack[-1]def getMin(self) -> int: return self.min_stack[-1]

不使用辅助栈只用一个栈也可以解决问题。
辅助栈的方法，是新增一个栈用来维护最小值。
而只用一个栈，就只需要新增一个变量来保存最小值。在数据出入栈的同时，通过一些方法，将最小值的变化记录在数据栈中。
方法一：

入栈 3 ||min = 3 || |_3_| stack入栈 5 ||min = 3 | 5 | |_3_| stack入栈 2 | 2 |min = 2? | 5 | |_3_| stack入栈2时，栈中最小值变成了2，如果直接将min跟新成2，那之前的最小值3就会丢失为了保存之前的最小值3，在入栈2时，先将之前最小值3入栈保存在栈中，然后在入栈2，更新min也就是，当新入栈的值，比之前的最小值还小，就将旧的最小值先保存到栈中，在入栈新的值，并且更新最小值为新入栈的值| 2 |min = 2 | 3 | | 5 | |_3_| stack入栈 6 | 6 |min = 2 | 2 | | 3 | | 5 | |_3_| stack出栈 6 | 2 |min = 2 | 3 | | 5 | |_3_| stack出栈 2 | 2 |min = 2 | 3 | | 5 | |_3_| stack出栈时，当前top元素，和当前min值相同时，说明当前top元素，在入栈时是更新了最小值的元素，也就是说它的下一个元素，是之前旧的min值所以，出栈2，出栈3，同时更新min=3作者：windliang 链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python代码

class MinStack:def __init__(self): self.stack = [] self.min = -1def push(self, val: int) -> None: if not self.stack: self.stack.append(val) self.min = val else: # 这里必须用<=，必须也要包含等于 # 比如依次push 0,1,0，push第3个0时，它等于最小值0， # 也需要先插入一个最小值到栈中 # 如果不这么做，pop 0的时候，0等于最小值，会认为前面的1是之前的最小值 # 但1只是正常push入栈的元素 if val <= self.min: self.stack.append(self.min) self.min = val self.stack.append(val)def pop(self) -> None: top = self.stack.pop() # 不要忘记pop后空栈的边界情况 self.stack if self.stack and top==self.min: self.min=self.stack.pop() return topdef top(self) -> int: return self.stack[-1]def getMin(self) -> int: return self.min

方法二：
原理和上面一样，只是操作上略有不同。
push的时候，不是直接存入值，而是存入值和当前最小值的差。
push时：

入栈值 > 最小值，push(入栈值-最小值)，最小值不变
入栈值 < 最小值，push(入栈值-旧最小值)，新最小值变为入栈值

pop时：

栈顶值 > 0，入栈值 = 栈顶值+最小值，最小值不变
栈顶值 < 0，入栈值 = 最小值，之前的最小值=入栈值-栈顶值=最小值-栈顶值

入栈 3，存入 3 - 3 = 0 ||min = 3 || |_0_| stack入栈 5，存入 5 - 3 = 2 ||min = 3 | 2 | |_0_| stack入栈 2，因为出现了更小的数，所以我们会存入一个负数，这里很关键也就是存入2 - 3 = -1, 并且更新 min = 2 对于之前的 min 值 3, 我们只需要用更新后的 min - 栈顶元素 -1 就可以得到 | -1|min = 2 | 5 | |_3_| stack入栈 6，存入6 - 2 = 4 | 4 |min = 2 | -1| | 5 | |_3_| stack出栈，返回的值就是栈顶元素 4 加上 min，就是 6 ||min = 2 | -1| | 5 | |_3_| stack出栈，此时栈顶元素是负数，说明之前对 min 值进行了更新。入栈元素 - min = 栈顶元素，入栈元素其实就是当前的 min 值 2 所以更新前的 min 就等于入栈元素 2 - 栈顶元素(-1) = 3 || min = 3 | 5 | |_3_| stack作者：windliang 链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python代码

class MinStack:def __init__(self): self.stack = [] self.min = -1def push(self, val: int) -> None: if not self.stack : self.min = val diff = val - self.min self.stack.append(diff) if diff < 0: self.min = valdef pop(self) -> None: diff = self.stack.pop() if diff < 0: top = self.min old_min = top - diff self.min = old_min else: top = self.min + diffreturn topdef top(self) -> int: diff = self.stack[-1] top = (diff + self.min) if diff>0 else self.min return topdef getMin(self) -> int: return self.min