剑指栈的min函数

维护了一个排序的栈。

    def __init__(self):
        self.stack=[]
        self.sortedstack=[]

    def push(self, node):
        # write code here
        self.sortedstack.append(node)
        self.stack.append(node)
        if len(self.sortedstack)>1:
            i=len(self.sortedstack)-1
            while i!=0:
                if self.sortedstack[i]<self.sortedstack[i-1]:
                    self.sortedstack[i],self.sortedstack[i-1]=self.sortedstack[i-1],self.sortedstack[i]
                    i=i-1
                else:
                    break


    def pop(self):
        # write code here

        value=self.stack[-1]
        self.stack=self.stack[:-1]
        print(self.sortedstack)
        if len(self.sortedstack)==1:
            self.sortedstack=[]

        else:
            left=0
            right=len(self.sortedstack)-1

            while left<=right:
                mid=(right-left)//2+left
                if self.sortedstack[mid]<value:
                    left=mid+1
                elif self.sortedstack[mid]>value:
                    right=mid-1
                elif self.sortedstack[mid]==value:
                    break
            print(mid)
            if mid == len(self.sortedstack)-1:
                self.sortedstack=self.sortedstack[:-1]
            else:
                for i in range(mid+1,len(self.sortedstack)):
                    self.sortedstack[i-1]=self.sortedstack[i]
                self.sortedstack=self.sortedstack[:-1]


        return value
    def top(self):
        # write code here
        return self.stack[-1]

    def getMin(self):
        # write code here
        return self.sortedstack[0]

因为求最小值需要遍历数组时间复杂度为o(n)，此题要求o(1)所以是一道空间换时间的题，需要维护一个当前最小值的栈，每次push元素的时候，也需要将当前的最小值放入最小值栈中，然后pop元素的时候也需要将对应的最小值pop出去。在pop的时候也要维护self.minvalue的变量值，如果数组没有值了，需要将其置为float('inf')。

# -*- coding:utf-8 -*-
def __init__(self): 
        self.stack=[]
        self.minstack=[]
        self.minvalue=float('inf')
    def push(self, node):
        # write code here
        self.stack.append(node)
        if node<=self.minvalue or  len(self.minstack)==0:
            self.minstack.append(node)
            self.minvalue=node
        else:
            self.minstack.append(self.minvalue)

    def pop(self):
        # write code here
        value=self.stack[-1]
        self.stack=self.stack[:-1]
        self.minstack=self.minstack[:-1]
        if len(self.minstack)==0:
            self.minvalue=float('inf')
        else:
            self.minvalue=self.minstack[-1]
        return value
    def top(self):
        # write code here
        return self.stack[-1]
    def getMin(self):
        # write code here
        return self.minstack[-1]

可以压缩最小值栈，当最小值相同的时候只存储一个就行，pop的时候，注意当两个栈顶的值都相同的时候才把最小值栈的元素pop出去，否则继续保留。注意最开始入栈float('inf')

class Solution:
    def __init__(self):
        self.stack=[]
        self.minstack=[float('inf')]
        self.minvalue=float('inf')
    def push(self, node):
        # write code here
        self.stack.append(node)
        if node<self.minvalue:
            self.minstack.append(node)
            self.minvalue=node


    def pop(self):
        # write code here
        value=self.stack[-1]
        self.stack=self.stack[:-1]
        if value==self.minstack[-1]:

            self.minstack=self.minstack[:-1]
        return value
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        if self.stack[-1]<self.minstack[-1]:
            return self.stack[-1]
        return self.minstack[-1]

只使用一个栈来完成任务，当入栈元素小于当前最小元素时说明当前的最小元素需要改变，所以将之前的最小元素也入栈，便于后面查找，当出栈的时候，当出栈值等于当前最小值的时候，说明当前的最小值需要改变，所以应该去找栈中之前的最小值。

class Solution:
    def __init__(self):
        self.stack=[]
        #self.minstack=[]
        self.minvalue=float('inf')
    def push(self, node):
        # write code here

        if node<=self.minvalue:
            self.stack.append(self.minvalue)
            #self.minstack.append(node)
            self.minvalue=node
        self.stack.append(node)


    def pop(self):
        # write code here
        value=self.stack[-1]
        self.stack=self.stack[:-1]
        if value==self.minvalue:
            self.minvalue=self.stack[-1]
            self.stack=self.stack[:-1]


        return value
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here

        return self.minvalue

存储入栈值与最小值之间的差值，起初设置最小值为float('inf'),当栈是空的时候，将最小值设置为最开始入栈的元素，然后先入栈当前值与最小值的差值，当当前值比最小值还要小的时候，更换最小值；当出栈的时候，判断当前元素是正数还是负数，如果是负数的话，就说明当前值小于最小值，所以需要更换最小值，通过value-=diff ，当差值是正数时，说明最小值不用更换。注意这种方法在返回top元素的时候不能简单的返回栈顶的元素，而是需要判断，当元素小于0时，说明当前的最小值就是栈顶的元素，当元素大于0需要使用最小值加上差值得到原来的元素。

这种情况存在 最大值减去最小值，会溢出的问题。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack=[]
        #self.minstack=[]
        self.minvalue=float('inf')

    def push(self, node):
        # write code here    
        if len(self.stack)==0:
            self.minvalue=node

        self.stack.append(node-self.minvalue)
        if self.minvalue>node:
            self.minvalue=node




    def pop(self):
        # write code here
        value=self.stack[-1]
        self.stack=self.stack[:-1]
        if value<0:
            self.minvalue=self.minvalue-value         
        return value
    def top(self):
        # write code here
        if self.stack[-1]<0:
            return self.minvalue
        return self.stack[-1]+self.minvalue
    def getMin(self):
        # write code here

       if len(self.stack)==0:
            return None
       return self.minvalue