leetcode155 最小栈

这道题的主要思路是：直接利用python的列表作为栈的实现。而如何实现每次只用O(1)的时间就能返回栈的最小元素呢？那就只能通过设置一个保存栈中最小元素下标的变量来实现。注意当pop出的元素是当前最小元素时，需要重新遍历一次栈得到最小元素下标。

简单题

import sys
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.min_index=None

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if len(self.stack)==0:
            self.stack.append(x)
            self.min_index=0
        else:
            self.stack.append(x)
            if x<self.stack[self.min_index]:
                self.min_index=len(self.stack)-1

    def pop(self):
        """
        :rtype: None
        """
        if self.min_index==len(self.stack)-1:
            pop_value=self.stack.pop()
            min_v=sys.maxint
            for i,v in enumerate(self.stack):
                if v<min_v:
                    min_v=self.stack[i]
                    self.min_index=i
        else:
            pop_value=self.stack.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.stack[len(self.stack)-1]
        

    def getMin(self):
        """
        :rtype: int
        """
        return self.stack[self.min_index]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()