关于数据结构与算法:每日leetcode155-最小栈

设计一个反对 push，pop，top 操作，并能在常数工夫内检索到最小元素的栈。

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

输入：[null,null,null,null,-3,null,0,-2]

题目要求在常熟工夫内能检索到最小元素，常数工夫就是 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 = -1

    def 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 top

    def 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 = -1

    def 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 = val

    def 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 + diff
        
        return top

    def top(self) -> int:
        diff = self.stack[-1]
        top = (diff + self.min) if diff>0 else self.min
        return top

    def getMin(self) -> int:
        return self.min

题目

思路

辅助栈

不应用辅助栈