155. 最小栈

https://leetcode-cn.com/problems/min-stack/

解法一：

主要就是维持一个指向最小元素的指针minIdx，这样getMin就能O（1），但是pop（）的处理过程还是用了O（n）

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []  #栈
        self.minIdx = -1  #最小元素下标
        
    def push(self, x: int) -> None:       
        self.stack.append(x)
        if self.minIdx == -1:
            self.minIdx = 0
        elif x < self.stack[self.minIdx]:  #更新最小下标
            self.minIdx = len(self.stack) - 1
                    
    def pop(self) -> None:
        if len(self.stack) == 1:
            self.minIdx = -1
        #若弹出元素是最小元素，则需更新最小下标
        elif len(self.stack)-1 == self.minIdx:
            self.minIdx = self.stack.index(min(self.stack[:-1]))        
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.stack[self.minIdx]

解法二：双栈

思路比较巧妙，一个stack存元素，一个idxStack存最小元素下标，两个栈长度相等，同步更新。

下标栈的栈顶idxStack[-1]存储当前stack的最小元素下标。

多用一个栈竟然内存消耗更少

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []  #栈
        self.idxStack = []  #最小元素下标栈
        
    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.stack) == 1:
            self.idxStack.append(0)
        else:
            if x < self.stack[self.idxStack[-1]]:                
                self.idxStack.append(len(self.stack)-1)
            else:
                self.idxStack.append(self.idxStack[-1])                    
        
    def pop(self) -> None:
        self.stack.pop()
        self.idxStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.stack[self.idxStack[-1]]