JZ30 包含min函数的栈

1. 解题思路

1.1 回顾栈的特性

只在一端 插入和删除数据，并且数据存在先进后出，后进先出的特性。

 核心代码

class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.min_stack:
            self.min_stack.append(node)
        elif self.min_stack[-1] > node:
            self.min_stack.append(node)
        else:
            self.min_stack.append(self.min_stack[-1])
           
    def pop(self):
        # write code here
        self.stack.pop()
        self.min_stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.min_stack[-1]

3.复杂度分析

• 时间复杂度：O(1) (由于每次入栈和出栈都只涉及栈顶元素的变动，所以是常量级O(1))
• 空间复杂度：O(n) (因为需要额外创建一个辅助栈stack_min)

------------------------------------------我是解法二的分割线-------------------------------------------

4. 解法二

4.1 思路

上面是辅助栈的解法，有没有不用辅助栈的解法？答案是肯定的！只需一个栈即可解决，核心思路用到了元组这个结构。即每次入栈和出栈都是一个元组，元组里面包含（当前数值x，栈内最小值）：

• top获取的就是元组的第一个值；
• min获取的就是元组的第二个值；
• pop就是删除栈顶的这个元组；
• push 则要分两种情况：
  • 第一种：栈空的时候，直接压入元组（数值x，栈内最小值也是x）；
  • 第二种：不为空，则比较两元组大小，取最小值压入（数值x，min(之前的栈内最小值，x)）。

4.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []  #初始化原栈
    def push(self, node):
        if not self.stack:
            #栈为空的情况，直接压入元组
            self.stack.append((node, node))
        #栈不为空的情况，取最小值压入
        else:
            self.stack.append((node, min(node, self.stack[-1][1])))
    def pop(self):
        self.stack.pop()                    #弹出栈顶元组
    def top(self):
        return self.stack[-1][0]                #栈顶元组的第一个值
    def min(self):
        return self.stack[-1][1]              #最小值就即元组的第二个值